Testing Simultaneous Planarity when the Common Graph is 2-Connected
Bernhard Haeupler, Krishnam Raju Jampani, Anna Lubiw · Journal of Graph Algorithms and Applications · 2013
Two planar graphs G1 and G2 sharing some vertices and edges are simultaneously planar if they have planar drawings such that a shared vertex [edge] is represented by the same point [curve] in both drawings. It is an open problem whether simultaneous planarity can be tested efficiently. We give a linear-time algorithm to test simultaneous planarity when the shared graph is 2-connected. Our algorithm extends to the case of k planar graphs where each vertex [edge] is either common to all graphs or belongs to exactly one of them, and the common subgraph is 2-connected.