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: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] [error in script]
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory

  • Subjects: 05-XX 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
    Deposit Information:
    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://e-archive.informatik.uni-koeln.de/id/eprint/707