Simultaneous Embedding of Planar Graphs with Few Bends - Erten, Cesim; Kobourov, Stephen (Journal of Graph Algorithms and Applications, 2005)
We consider several variations of the simultaneous embedding problemfor planar graphs. We begin with a simple proof that not all pairs ofplanar graphs have simultaneous geometric embeddings. However, usingbends, pairs of planar graphs can be simultaneously embedded on theO(n2)×O(n2) grid, with at most three bends per edge, wheren is the number of vertices. The O(n) time algorithm guaranteesthat two corresponding vertices in the graphs are mapped to the samelocation in the final drawing and that both the drawings are withoutcrossings. <!----> The special case when both input graphs are trees has severalapplications, such as contour tree simplification and evolutionarybiology. We show that if both input graphs are trees, only onebend per edge is required. The O(n) time algorithm guarantees thatboth drawings are crossings-free, corresponding tree vertices aremapped to the same locations, and all vertices (and bends) are on theO(n2)×O(n2) grid (O(n3)×O(n3) grid). <!----> For the special case when one of the graphs is a tree and the other isa path we can find simultaneous embeddings with fixed-edges. That is,we can guarantee that corresponding vertices are mapped to the samelocations and that corresponding edges are drawn the same way. Wedescribe an O(n) time algorithm for simultaneous embeddings withfixed-edges for tree-path pairs with at most one bend per tree-edgeand no bends along path edges, such that all vertices (and bends) areon the O(n)×O(n2) grid, (O(n2)×O(n3) grid). <!---->