Characterizations of Restricted Pairs of Planar Graphs allowing Simultaneous Embeddings with Fixed Edges

Fowler, J. Joseph and Jünger, Michael and Kobourov, Stephen G. and Schulz, Michael (2008) Characterizations of Restricted Pairs of Planar Graphs allowing Simultaneous Embeddings with Fixed Edges.
Published In: Workshop on Graph-Theoretic Concepts in Computer Science 2008, Lecture notes in computer science. 5344 Springer 2008, pp. 146-158.

Abstract

A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V in the Euclidean plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same simple curve in the simultaneous drawing. Determining in polynomial time which pairs of graphs share a simultaneous embedding with fixed edges (SEFE) has been open. We give a necessary and sufficient condition for whether a SEFE exists for pairs of graphs whose union is homeomorphic to K5 or K3,3 . 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 efficient algorithms to compute a SEFE. Finally, we provide a linear-time decision algorithm for deciding whether a pair of biconnected outerplanar graphs has a SEFE.


Actions:
Download: [img] PDF - Preprinted Version
Download (275kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: [error in script] [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory

  • Additional Information: an extended journal version is accepted for publication in Computational Geometry: Theory and Applications, Elsevier, 2011.
    Uncontrolled Keywords: simultaneous Geometric Graph Embeddings
    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: 14 Mar 2011 00:00
    Last Modified: 09 Jan 2012 12:48
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Prof. Dr. Michael Jünger
    Date Deposited: 14 Mar 2011 00:00
    Last Modified: 09 Jan 2012 12:48
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/584