"Simultaneous Geometric Graph Embeddings"
Article by Alejandro Estrella-Balderrama, Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz, available as BibTeX Source and in portable document format.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2006-523
Keywords:	complexity result, planar graphs, Simultaneous Geometric Graph Embeddings
MSC codes:	05C10, 05C62
This article is to appear in "15th International Symposium on Graph Drawing".
Abstract:	We consider the following problem known as simultaneous geometric graph embedding (SGE). Given a set of planar graphs on a shared vertex set, decide whether the vertices can be placed in the plane in such a way that for each graph the straight-line drawing is planar. We partially settle an open problem of Erten and Kobourov and show that even for two graphs the problem is NP-hard. We also show that the problem of computing the rectilinear crossing number of a graph can be reduced to a simultaneous geometric graph embedding problem; this implies that placing SGE in NP will be hard, since the corresponding question for rectilinear crossing number is a longstanding open problem. However, rather like rectilinear crossing number, SGE can be decided in PSPACE.