Testing Simultaneous Planarity when the Common Graph is 2-Connected

Abstract

Two planar graphs G₁ and G₂ 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.