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: Graph-theoretic 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. 325-335.


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 NP-complete even for three planar graphs. For two planar graphs the complexity status is still open.

Download: [img] Postscript - Preprinted Version
Download (669kB) | Preview
Download: [img] PDF - Preprinted Version
Download (165kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2006-507
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 18 Jan 2008 00:00
Last Modified: 12 Jan 2012 10:13