Simultaneous Embedding of Embedded Planar Graphs
Angelini, Patrizio
Di Battista, Giuseppe Frati, Fabrizio
Di Battista, Giuseppe
Frati, Fabrizio
Citations
Altmetric:
Abstract
A simultaneous embedding with fixed edges (SEFE) of a set of k planar graphs G1,…,Gk on the same set of vertices is a set of k planar drawings of G1,…,Gk, respectively, such that each vertex is placed on the same point in all the drawings and each edge is represented by the same Jordan curve in the drawings of all the graphs it belongs to. A simultaneous geometric embedding (SGE) is a SEFE in which the edges are represented by straight-line segments.
Given k planar graphs G1,…,Gk, deciding whether they admit a SEFE and whether they admit an SGE are NP-hard problems, for k ≥ 3 and for k ≥ 2, respectively.
In this paper we consider the complexity of SEFE and of SGE when the graphs G1,…,Gk have a fixed planar embedding.
In sharp contrast with the NP-hardness of SEFE for three non-embedded planar graphs, we show that SEFE is quadratic-time solvable for three graphs with a fixed planar embedding.
Furthermore, we show that, given k embedded planar graphs G1,…,Gk, deciding whether a SEFE of G1,…,Gk exists and deciding whether an SGE of G1,…,Gk exists are NP-hard problems, for k ≥ 14 and k ≥ 13, respectively.
Description
Date
2011
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Simultaneous embedding, Planar graphs, Planar embeddings, NP-hardness
Citation
Angelini, Patrizio, Giuseppe Di Battista, and Fabrizio Frati. 2013. “Simultaneous Embedding of Embedded Planar Graphs.” International Journal of Computational Geometry and Applications 23 (2): 93–126. 2013.