Universität zu Köln

Fowler, J. Joseph, Jünger, Michael, Kobourov, Stephen G. and Schulz, Michael (2008). Characterizations of Restricted Pairs of Planar Graphs allowing Simultaneous Embeddings with Fixed Edges. In: Workshop on Graph-Theoretic Concepts in Computer Science 2008, pp. 146-158. Springer.

Preview

PDF zaik2009-584.pdf - Submitted Version Download (275kB) | Preview

Abstract

A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V in the Euclidean plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same simple curve in the simultaneous drawing. Determining in polynomial time which pairs of graphs share a simultaneous embedding with ?xed edges (SEFE) has been open. We give a necessary and su?cient condition for whether a SEFE exists for pairs of graphs whose union is homeomorphic to K5 or K3,3 . This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide e?cient algorithms to compute a SEFE. Finally, we provide a linear-time decision algorithm for deciding whether a pair of biconnected outerplanar graphs has a SEFE.

Item Type:	Book Section
Creators:	Creators Email ORCID ORCID Put Code Fowler, J. Joseph UNSPECIFIED UNSPECIFIED UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Kobourov, Stephen G. UNSPECIFIED UNSPECIFIED UNSPECIFIED Schulz, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549847
Title of Book:	Workshop on Graph-Theoretic Concepts in Computer Science 2008
Series Name:	Lecture notes in computer science
Volume:	5344
Page Range:	pp. 146-158
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/54984