Disconnectivity and relative positions in simultaneous embeddings

For two planar graphs G①=(V①,E①)G①=(V①,E①) and G②=(V②,E②)G②=(V②,E②) sharing a common subgraph G=G①∩G②G=G①∩G② the problem Simultaneous Embedding with Fixed Edges (SEFE) asks whether they admit planar drawings such that the common graph is drawn the same. Previous algorithms only work for cases where G is connected, and hence do not need to handle relative positions of connected components. We consider the problem where G  , G①G① and G②G② are not necessarily connected.First, we show that a general instance of SEFE can be reduced in linear time to an equivalent instance where V①=V②V①=V② and G①G① and G②G② are connected. Second, for the case where G consists of disjoint cycles, we introduce the CC-tree which represents all embeddings of G   that extend to planar embeddings of G①G①. We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for SEFE if all k   input graphs (possibly k>2k>2) pairwise share the same set of disjoint cycles. These results, including the CC-tree, extend to the case where G   consists of arbitrary connected components, each with a fixed planar embedding on the sphere. Then the running time is O(n2)O(n2).