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

A set of planar graphs {^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 ^Ei does not cross any other edge in ^Ei (except at endpoints) for i∈{1,⋯,k}. A fixed edge is an edge (u,v) that is drawn using the same simple curve for each graph ^Gi whose edge set ^Ei contains the edge (u,v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to ^K5 or K3 _,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(ⁿ⁴)-time algorithms to compute a SEFE.