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; Jul2012, Vol. 14, p150-172, 23p
- Publication Year :
- 2012
-
Abstract
- Abstract: In this paper we study the time complexity of the problem Simultaneous Embedding with Fixed Edges (Sefe), that takes two planar graphs and as input and asks whether a planar drawing of and a planar drawing of exist such that: (i) each vertex is mapped to the same point in and in ; (ii) every edge is mapped to the same Jordan curve in and . First, we give a linear-time algorithm for Sefe when the intersection graph of and , that is the planar graph , is biconnected. Second, we show that Sefe, when 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 is a star. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 15708667
- Volume :
- 14
- Database :
- Supplemental Index
- Journal :
- Journal of Discrete Algorithms
- Publication Type :
- Academic Journal
- Accession number :
- 75186349
- Full Text :
- https://doi.org/10.1016/j.jda.2011.12.015