Simultaneous embedding: edge orderings, relative positions, cutvertices
- T. Bläsius,
- A. Karrer,
- I. Rutter
- University of Potsdam,
- Karlsruhe Institute of Technology,
- ,
Information
Output type
Original language
EnglishPages from-to (Number of pages)
Pages 1214-1277 (64 pages)Journal (Volume, Issue Number)
Algorithmica (Volume 80, Issue 4)Publication milestones
- Accepted/In press - 15/03/2017
- Published - 01/04/2018
Publication status
ISSN
0178-4617Abstract
A simultaneous embedding (with fixed edges) of two graphs G1 and G2 with common graph G=G1∩G2 is a pair of planar drawings of G1 and G2 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∪=G1∪G2, (2) most separating pairs of G ∪, and (3) connected components of G that are biconnected but not a cycle. Second, we give an O(n 3) -time algorithm solving Sefe for instances with the following restriction. Let u be a pole of a P-node μ in the SPQR-tree of a block of G1 or G2. Then at most three virtual edges of μ may contain common edges incident to u. All algorithms extend to the sunflower case, i.e., to the case of more than two graphs pairwise intersecting in the same common graph.
