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 @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.