Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
Angelini, Patrizio
Di Battista, Giuseppe Frati, Fabrizio Patrignani, Maurizio Rutter, Ignaz
Di Battista, Giuseppe
Frati, Fabrizio
Patrignani, Maurizio
Rutter, Ignaz
Citations
Altmetric:
Abstract
In this paper we study the time complexity of the problem Simultaneous Embedding with Fixed Edges (Sefe), that takes two planar graphs G1 = (V,E1) and G2 = (V,E2) as input and asks whether a planar drawing Γ1 of G1 and a planar drawing Γ2 of G2 exist such that: (i) each vertex v ∈ V is mapped to the same point in Γ1 and in Γ2; (ii) every edge e ∈ E1 ∩E2 is mapped to the same Jordan curve in Γ1 and Γ2. First, we give a linear-time algorithm for Sefe when the intersection graph of G1 and G2, that is the planar graph G1∩2 = (V,E1 ∩ E2), isbiconnected. Second, we show that Sefe, when G1∩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 G1∩2 is a star.
Description
Date
2012
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Simultaneous embedding, Planarity, Linear-time algorithm, SPQR-trees
Citation
Angelini, Patrizio, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Ignaz Rutter. “Testing the Simultaneous Embeddability of Two Graphs Whose Intersection Is a Biconnected or a Connected Graph.” Journal of Discrete Algorithms 14: 150–72. 2012.