"Characterizing 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-583
Keywords:	Simultaneous Geometric Graph Embeddings
MSC codes:	05C10
This article was published in 2008 in the journal "Electronic Notes in Discrete Mathematics", volume 31, pages 41-44.
Abstract:	A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V in the plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same Jordan curve in the simultaneous drawings. While any number of planar graphs have a simultaneous embedding without fixed edges, determining which graphs always share a simultaneous embedding with fixed edges (SEFE) has been open. We partially close this problem by giving a necessary condition to determine when pairs of graphs have a SEFE.