Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph

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 Gamma(1) of G(1) and a planar drawing Gamma(2) of G(2) exist such that: (i) each vertex v. V is mapped to the same point in Gamma(1) and in Gamma(2); (ii) every edge e is an element of E-1 boolean AND E-2 is mapped to the same Jordan curve in Gamma(1) and Gamma(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 boolean AND 2) = (V, E-1 boolean AND E-2), is biconnected. Second, we show that Sefe, when G(1 boolean AND 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 boolean AND 2) is a star. (C) 2011 Elsevier B.V. All rights reserved.