# Disconnectivity and Relative Positions in Simultaneous Embeddings

Bläsius, Thomas and Rutter, Ignaz (2013) Disconnectivity and Relative Positions in Simultaneous Embeddings. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 31-42(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.

## Abstract

For two planar graph \$G^{\textcircled1}\$ = (\$V^{\textcircled1}\$, \$E^{\textcircled1}\$) and \$G^{\textcircled2}\$ = (\$V^{\textcircled2}\$, \$E^{\textcircled2}\$) sharing a common subgraph G = \$G^{\textcircled1}\$ ∩ \$G^{\textcircled2}\$ 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^{\textcircled1}\$ and \$G^{\textcircled2}\$ 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^{\textcircled1}\$ = \$V^{\textcircled2}\$ and \$G^{\textcircled1}\$ and \$G^{\textcircled2}\$ 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^{\textcircled1}\$. 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>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 embedding. Then the running time is O(n^2).

Item Type: Conference Paper 10.1007/978-3-642-36763-2_4 G Algorithms and Complexity > G.490 Embeddings http://gdea.informatik.uni-koeln.de/id/eprint/1295