Intersection Graphs in Simultaneous Embedding with Fixed Edges

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

Abstract

We examine the simultaneous embedding with fixed 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 fixed edges for (G1 , G2 ). More formally, we define 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 fixed edges. We will characterize this set by a detailed study of topological embeddings and finally give a complete list of graphs in this set as our main result of this paper.


Actions:
Download: [img] PDF - Preprinted Version
Download (165Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2009-586
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 11 May 2010 00:00
Last Modified: 09 Jan 2012 15:40
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/586