Simultaneous Embedding of Planar Graphs with Few Bends

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(n²)×O(n²) 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(n²)×O(n²) grid (O(n³)×O(n³) 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(n²) grid, (O(n²)×O(n³) grid).