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 (162kB)  Preview 

Export as:  [error in script] 
Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  [error in script] 30 (Google Scholar)  [error in script] 
Uncontrolled Keywords:  [error in script] 
Subjects: 

Uncontrolled Keywords:  Simultaneous Geometric Graph Embeddings, planar graphs, complexity result 
Subjects:  05XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory 05XX Combinatorics > 05Cxx Graph theory > 05C62 Graph representations (geometric and intersection representations, etc.) 
Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Depositing User:  Prof. Dr. Michael Jünger 
Date Deposited:  06 Apr 2009 00:00 
Last Modified:  09 Jan 2012 15:47 
ZAIK Number:  [error in script] 

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 