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 G1=(V,E1)G1=(V,E1) and G2=(V,E2)G2=(V,E2) as input and asks whether a planar drawing Γ1Γ1 of G1G1 and a planar drawing Γ2Γ2 of G2G2 exist such that: (i) each vertex v∈Vv∈V is mapped to the same point in Γ1Γ1 and in Γ2Γ2; (ii) every edge e∈E1∩E2e∈E1∩E2 is mapped to the same Jordan curve in Γ1Γ1 and Γ2Γ2.First, we give a linear-time algorithm for Sefe when the intersection graph   of G1G1 and G2G2, that is the planar graph G1∩2=(V,E1∩E2)G1∩2=(V,E1∩E2), is biconnected. Second, we show that Sefe, when G1∩2G1∩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∩2G1∩2 is a star.