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 Γ1 of G 1 and a planar drawing Γ2 of G 2 exist such that: (i) each vertex v ∈ V is mapped to the same point in Γ1 and in Γ2; (ii) every edge e ∈ E 1 ∩ E 2 is mapped to the same Jordan curve in Γ1 and Γ2. First, we show a polynomial-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 a tree, is equivalent to a suitably-defined book embedding problem. Based on such an 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.