Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges

Fowler, J. Joseph and Jünger, Michael and Kobourov, Stephen G. and Schulz, Michael (2011) Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges.
Published in: Computational Geometry : Theory and Applications Vol. 44 (8). pp. 385-398. ISSN 0925-7721

Abstract

A set of planar graphs {G1(V,E1),…,Gk(V,Ek)} admits a simultaneous embedding if they can be drawn on the same pointset P of order n in the Euclidean plane such that each point in P corresponds one-to-one to a vertex in V and each edge in Ei does not cross any other edge in Ei (except at endpoints) for i∈{1,…,k}. A fixed edge is an edge (u,v) that is drawn using the same simple curve for each graph Gi whose edge set Ei contains the edge (u,v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to K5 or K3,3 to admit a simultaneous embedding with fixed edges (SEFE). 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 O(n4)-time algorithms to compute a SEFE.


Actions:
Full text not available from this repository.
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: UNSPECIFIED
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 03 Sep 2013 13:35
Last Modified: 03 Sep 2013 13:35
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/707