Back to Search
Start Over
Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
- Source :
- Journal of Discrete Algorithms. :150-172
- Publisher :
- Elsevier B.V.
-
Abstract
- In this paper we study the time complexity of the problem Simultaneous Embedding with Fixed Edges (Sefe), that takes two planar graphs G"1=(V,E"1) and G"2=(V,E"2) as input and asks whether a planar drawing @C"1 of G"1 and a planar drawing @C"2 of G"2 exist such that: (i) each vertex v@?V is mapped to the same point in @C"1 and in @C"2; (ii) every edge e@?E"1@?E"2 is mapped to the same Jordan curve in @C"1 and @C"2. First, we give a linear-time algorithm for Sefe when the intersection graph of G"1 and G"2, that is the planar graph G"1"@?"2=(V,E"1@?E"2), is biconnected. Second, we show that Sefe, when G"1"@?"2 is connected, is equivalent to a suitably-defined book embedding problem. Based on this equivalence and on recent results by Hong and Nagamochi, we show a linear-time algorithm for the Sefe problem when G"1"@?"2 is a star.
- Subjects :
- Vertex (graph theory)
Discrete mathematics
SPQR tree
Book embedding
Simultaneous embedding
Linear-time algorithm
Intersection graph
Jordan curve theorem
Planarity testing
Planar graph
Theoretical Computer Science
Combinatorics
symbols.namesake
Computational Theory and Mathematics
symbols
Discrete Mathematics and Combinatorics
Planarity
SPQR-tree
Connectivity
Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 15708667
- Database :
- OpenAIRE
- Journal :
- Journal of Discrete Algorithms
- Accession number :
- edsair.doi.dedup.....7504815de88c802e5bf4d9afa408df88
- Full Text :
- https://doi.org/10.1016/j.jda.2011.12.015