Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Twelfth International Symposium on Graph Drawing, GD 2004
DOI: 10.7155/jgaa.00113
Simultaneous Embedding of Planar Graphs with Few Bends
Vol. 9, no. 3, pp. 347-364, 2005. Regular paper.
Abstract We consider several variations of the simultaneous embedding problem
for planar graphs. We begin with a simple proof that not all pairs of
planar graphs have simultaneous geometric embeddings. However, using
bends, pairs of planar graphs can be simultaneously embedded on the
O(n2)×O(n2) grid, with at most three bends per edge, where
n is the number of vertices. The O(n) time algorithm guarantees
that two corresponding vertices in the graphs are mapped to the same
location in the final drawing and that both the drawings are without
crossings.
The special case when both input graphs are trees has several
applications, such as contour tree simplification and evolutionary
biology. We show that if both input graphs are trees, only one
bend per edge is required. The O(n) time algorithm guarantees that
both drawings are crossings-free, corresponding tree vertices are
mapped to the same locations, and all vertices (and bends) are on the
O(n2)×O(n2) grid (O(n3)×O(n3) grid).
For the special case when one of the graphs is a tree and the other is
a path we can find simultaneous embeddings with fixed-edges. That is,
we can guarantee that corresponding vertices are mapped to the same
locations and that corresponding edges are drawn the same way. We
describe an O(n) time algorithm for simultaneous embeddings with
fixed-edges for tree-path pairs with at most one bend per tree-edge
and no bends along path edges, such that all vertices (and bends) are
on the O(n)×O(n2) grid, (O(n2)×O(n3) grid).
|
Journal Supporters
|