Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges

A set of planar graphs {G1(V,E1),…,Gk(V,Ek)}{G1(V,E1),…,Gk(V,Ek)} admits a simultaneous embedding if they can be drawn on the same pointset P of order n in the Euclidean plane such that each point in P corresponds one-to-one to a vertex in V   and each edge in EiEi does not cross any other edge in EiEi (except at endpoints) for i∈{1,…,k}i∈{1,…,k}. A fixed edge   is an edge (u,v)(u,v) that is drawn using the same simple curve for each graph GiGi whose edge set EiEi contains the edge (u,v)(u,v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to K5K5 or K3,3K3,3 to admit a simultaneous embedding with fixed edges (SEFE). This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide O(n4)O(n4)-time algorithms to compute a SEFE.