Simultaneous Geometric Graph Embeddings

Estrella-Balderrama, Alejandro and Gassner, Elisabeth and Jünger, Michael and Percan, Merijam and Schaefer, Marcus and Schulz, Michael (2008) Simultaneous Geometric Graph Embeddings.
Published In: Graph drawing : 15th international symposium, GD 2007, Sydney, Australia, September 24 - 26, 2007 ; revised papers, Lecture Notes in Computer Science. 4875 Springer 2008, pp. 280-290.


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.

Download: [img] PDF - Preprinted Version
Download (162kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2006-523
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 06 Apr 2009 00:00
Last Modified: 09 Jan 2012 15:47