Universität zu Köln

Gassner, Elisabeth, Jünger, Michael, Percan, Merijam, Schaefer, Marcus and Schulz, Michael (2006). Simultaneous Graph Embeddings with Fixed Edges. In: Graph-theoretic concepts in computer science : 32nd international workshop, WG 2006, Bergen, Norway, June 22 - 24, 2006 ; revised papers, pp. 325-335. Springer.

Preview

PDF zaik2006-507.pdf - Draft Version Download (165kB) | Preview

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

Item Type:	Book Section, Proceedings Item or annotation in a legal commentary
Creators:	Creators Email ORCID ORCID Put Code Gassner, Elisabeth UNSPECIFIED UNSPECIFIED UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Percan, Merijam UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaefer, Marcus UNSPECIFIED UNSPECIFIED UNSPECIFIED Schulz, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548858
Title of Book:	Graph-theoretic concepts in computer science : 32nd international workshop, WG 2006, Bergen, Norway, June 22 - 24, 2006 ; revised papers
Series Name:	Lecture Notes in Computer Science
Volume:	4271
Page Range:	pp. 325-335
Date:	2006
Publisher:	Springer
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54885