"Simultaneous Graph Embeddings with Fixed Edges"
Article by Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz, available as BibTeX Source, postscript file, compressed postscript file and in portable document format.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2006-507
Keywords:	crossing number, graph drawing, simultaneous graph embeddings, weak realizibility
MSC codes:	05C10, 05C62
This article is to appear in "32nd International Workshop on Graph-Theoretic Concepts in Computer Science".
Abstract:	We study the problem of simultaneously embedding several graphs on the same vertex set in such a way that edges common to two or more graphs are represented by the same curve. This problem is known as simultaneously embedding graphs with fixed edges. We show that this problem is closely related to the weak realizability problem: Can a graph be drawn such that all edge crossings occur in a given set of edge pairs? By exploiting this relationship we can explain why the simultaneous embedding problem is challenging, both from a computational and a combinatorial point of view. More precisely, we prove that simultaneously embedding graphs with fixed edges is NP-complete even for three planar graphs. For two planar graphs the complexity status is still open.