"Characterizations of Restricted Pairs of Planar Graphs allowing Simultaneous Embeddings with Fixed Edges"
Article by J. Joseph Fowler, Michael Jünger, Stephen G. Kobourov, Michael Schulz, available as BibTeX Source and in portable document format.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2009-584
Keywords:	Simultaneous Geometric Graph Embeddings
MSC codes:	05C10
This article was published in 2008 by Springer-Verlag in the proceedings "Workshop on Graph-Theoretic Concepts in Computer Science 2008" (edited by H. Broersma, T. Erlebach, T. Friedetzky, and D. Paulusma), volume 5344, pages 146-158.
Abstract:	A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V in the Euclidean plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same simple curve in the simultaneous drawing. Determining in polynomial time which pairs of graphs share a simultaneous embedding with fixed edges (SEFE) has been open. We give a necessary and sufficient condition for whether a SEFE exists for pairs of graphs whose union is homeomorphic to K5 or K3,3 . 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 efficient algorithms to compute a SEFE. Finally, we provide a linear-time decision algorithm for deciding whether a pair of biconnected outerplanar graphs has a SEFE.