Simultaneous Geometric Graph Embeddings
EstrellaBalderrama, 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. 280290.
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 straightline drawing is planar. We partially settle an open problem of Erten and Kobourov and show that even for two graphs the problem is NPhard. 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: 
PDF
 Preprinted Version
Download (158Kb)  Preview 

Export as:  
Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  30 (Google Scholar)  7 (Web of Science) 
Uncontrolled Keywords:  Simultaneous Geometric Graph Embeddings planar graphs complexity result 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  zaik2006523 

Depositing User:  Prof. Dr. Michael Jünger 
Date Deposited:  06 Apr 2009 00:00 
Last Modified:  09 Jan 2012 15:47 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/523 