Disconnectivity and Relative Positions in Simultaneous EmbeddingsBläsius, Thomas and Rutter, Ignaz (2013) Disconnectivity and Relative Positions in Simultaneous Embeddings. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 3142(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractFor 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 CCtree which represents all embeddings of G that extend to planar embeddings of $G^{\textcircled1}$. We show that CCtrees can be computed in linear time, and that their intersection is again a CCtree. This yields a lineartime algorithm for SEFE if all k input graphs (possibly k>2) pairwise share the same set of disjoint cycles. These results, including the CCtree, extend to the case where G consists of arbitrary connected components, each with a fixed embedding. Then the running time is O(n^2).
Actions (login required)
