Characterizing Simultaneous Embeddings with Fixed Edges

Fowler, J. Joseph and Jünger, Michael and Kobourov, Stephen G. and Schulz, Michael (2008) Characterizing Simultaneous Embeddings with Fixed Edges.
Published in: Electronic Notes in Discrete Mathematics Vol. 31. pp. 41-44.

Abstract

A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V in the plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same Jordan curve in the simultaneous drawings. While any number of planar graphs have a simultaneous embedding without fixed edges, determining which graphs always share a simultaneous embedding with fixed edges (SEFE) has been open. We partially close this problem by giving a necessary condition to determine when pairs of graphs have a SEFE.


Actions:
Download: [img] PDF - Preprinted Version
Download (759kB) | Preview
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]
Uncontrolled Keywords: [error in script]
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory

  • 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: 06 Apr 2009 00:00
    Last Modified: 09 Jan 2012 15:55
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Prof. Dr. Michael Jünger
    Date Deposited: 06 Apr 2009 00:00
    Last Modified: 09 Jan 2012 15:55
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/583