Universität zu Köln

Estrella-Balderrama, Alejandro, Gassner, Elisabeth, Jünger, Michael, Percan, Merijam, Schaefer, Marcus and Schulz, Michael (2008). Simultaneous Geometric Graph Embeddings. In: Graph drawing : 15th international symposium, GD 2007, Sydney, Australia, September 24 - 26, 2007 ; revised papers, pp. 280-290. Springer.

Preview

PDF zaik2006-523.pdf - Submitted Version Download (162kB) | Preview

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 straight-line drawing is planar. We partially settle an open problem of Erten and Kobourov and show that even for two graphs the problem is NP-hard. 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.

Item Type:	Book Section, Proceedings Item or annotation in a legal commentary
Creators:	Creators Email ORCID ORCID Put Code Estrella-Balderrama, Alejandro UNSPECIFIED UNSPECIFIED UNSPECIFIED 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-549004
Title of Book:	Graph drawing : 15th international symposium, GD 2007, Sydney, Australia, September 24 - 26, 2007 ; revised papers
Journal or Publication Title:	submitted to: submitted to:
Series Name:	Lecture Notes in Computer Science
Volume:	4875
Page Range:	pp. 280-290
Date:	2008
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/54900