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

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]