Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices

Bläsius, Thomas and Karrer, Annette and Rutter, Ignaz (2013) Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 220-231(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_20).

Full text not available from this repository.

Abstract

A simultaneous embedding of two graphs G\textcircled{1} and G\textcircled{2} with common graph G=G\textcircled{1}∩G\textcircled{2} is a pair of planar drawings of G\textcircled{1} and G\textcircled{2} that coincide on G. It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph G\textcircled{1}∪G\textcircled{2} , (2) cutvertices that are simultaneously a cutvertex in G\textcircled{1} and G\textcircled{2} and that have degree at most 3 in G, and (3) connected components of G that are biconnected but not a cycle. Second, we give an O(n 2)-time algorithm for Sefe where, for each pole u of a P-node μ (of a block) of the input graphs, at most three virtual edges of μ contain common edges incident to u. All algorithms extend to the sunflower case.

Item Type: Conference Paper G Algorithms and Complexity > G.490 EmbeddingsM Methods > M.600 PlanarP Styles > P.999 Others http://gdea.informatik.uni-koeln.de/id/eprint/1377