A Note on Simultaneous Embedding of Planar Graphs (Abstract)
Emilio Di Giacomo, Giuseppe Liotta · 2005
Let G1 and G2 be a pair of planar graphs such that V (G1) = V (G2) = V . A simultaneous embedding [6] Ψ = (Γ1,Γ2) of G1 and G2 is a pair of crossing-free drawings Γ1 and Γ2 of G1 and G2, respectively, such that for every vertex v ∈ V we have Γ1(v) = Γ2(v). If every edge e ∈ E(G1) ∩ E(G2) is represented with the same simple open Jordan curve both in Γ1 and in Γ2 we say that Ψ is a simultaneous embedding with fixed edges. If the edges of G1 and G2 are represented with straight-line segments in Γ1 and Γ2 we say that Ψ is a simultaneous geometric embedding. The existence of simultaneous geometric embeddings for pairs of paths, cycles, and caterpillars is shown in [2], where also counter-examples for pairs of general planar graphs, pairs of outerplanar graphs, and triples of paths are presented. Concerning the the computation of (non-geometric) simultaneous embeddings, Erten and Kobourov [6] presented an O(n)-time algorithm to simultaneously embed any pair of planar graphs on the O(n2)×O(n2) grid with at most three bends per edge, where n is the number of vertices of G1 and G2. If the two graphs are trees then the number of bends per edge can be reduced to one. Furthermore, in [6] an O(n)-time algorithm to compute a simultaneous embedding with fixed edges of a tree and a path on the O(n)×O(n2) grid with no bends on the path-edges and at most one bend per edge on the tree-edges is described. In this note we revisit the elegant technique of Erten and Kobourov [6] to present some new results on simultaneous embeddings with fixed edges. We prove that the pairs outerplanar graph path and outerplanar graph cycle admit a simultaneous embedding with fixed edges and at most one bend per edge. For the pair outerplanar graph path, the edges of the path are straight-line segments. We also present some extensions of the results in [6] about simultaneous embeddings of planar graphs that are immediate consequence of existing literature. For reasons of space some proof are sketched or omitted.