Universität zu Köln

Jünger, Michael and Schulz, Michael (2009). Intersection Graphs in Simultaneous Embedding with Fixed Edges. Journal of Graph Algorithms and Applications, 13 (2). pp. 205-218. Brown University.

Preview

PDF zaik2009-586.pdf - Submitted Version Download (169kB) | Preview

Abstract

We examine the simultaneous embedding with ?xed edges problem for two planar graphs G1 and G2 with the focus on their in- tersection S := G1 ? G2 . In particular, we will present the complete set of intersection graphs S that guarantee a simultaneous embedding with ?xed edges for (G1 , G2 ). More formally, we de?ne the subset ISEFE of all planar graphs as follows: A graph S lies in ISEFE if every pair of pla- nar graphs (G1 , G2 ) with intersection S = G1 ? G2 has a simultaneous embedding with ?xed edges. We will characterize this set by a detailed study of topological embeddings and ?nally give a complete list of graphs in this set as our main result of this paper.

Item Type:	Article
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Schulz, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549866
Journal or Publication Title:	Journal of Graph Algorithms and Applications
Volume:	13
Number:	2
Page Range:	pp. 205-218
Date:	2009
Publisher:	Brown University
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/54986