Simultaneous Graph Embeddings with Fixed Edges
Gassner, Elisabeth and Jünger, Michael and Percan, Merijam and Schaefer, Marcus and Schulz, Michael
(2006)
Simultaneous Graph Embeddings with Fixed Edges.
Published In:
Graphtheoretic concepts in computer science : 32nd international workshop, WG 2006, Bergen, Norway, June 22  24, 2006 ; revised papers, Lecture Notes in Computer Science. 4271 Springer 2006, pp. 325335.
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 NPcomplete even for three planar graphs. For two planar graphs the complexity status is still open.
Download: 
Postscript
 Preprinted Version
Download (669kB)  Preview 

Download: 
PDF
 Preprinted Version
Download (165kB)  Preview 
Export as:  [error in script] 
Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

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

Uncontrolled Keywords:  crossing number, graph drawing, simultaneous graph embeddings, weak realizibility 
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:  18 Jan 2008 00:00 
Last Modified:  12 Jan 2012 10:13 
ZAIK Number:  [error in script] 

Depositing User:  Prof. Dr. Michael Jünger 
Date Deposited:  18 Jan 2008 00:00 
Last Modified:  12 Jan 2012 10:13 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/507 