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. 385398.
ISSN 09257721
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 onetoone 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.
Item Type:  Article 

Citations:  [error in script] [error in script] 
Subjects: 

Subjects:  05XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory 
Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Depositing User:  Prof. Dr. Michael Jünger 
Date Deposited:  03 Sep 2013 13:35 
Last Modified:  03 Sep 2013 13:35 
ZAIK Number:  [error in script] 

Depositing User:  Prof. Dr. Michael Jünger 
Date Deposited:  03 Sep 2013 13:35 
Last Modified:  03 Sep 2013 13:35 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/707 