An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges

Fowler, J. Joseph and Gutwenger, Carsten and Jünger, Michael and Mutzel, Petra and Schulz, Michael (2009) An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges.
Published In: Graph Drawing GD 2008 Crete, Lecture notes in computer science. 5417 Springer-Verlag 2009, pp. 157-168.

Abstract

We present a linear-time algorithm for solving the simulta- neous embedding problem with fixed edges (SEFE) for a planar graph and a pseudoforest (a graph with at most one cycle) by reducing it to the following embedding problem: Given a planar graph G, a cycle C of G, and a partitioning of the remaining vertices of G, does there exist a planar embedding in which the induced subgraph on each vertex partite of G C is contained entirely inside or outside C ? For the latter prob- lem, we present an algorithm that is based on SPQR-trees and has linear running time. We also show how we can employ SPQR-trees to decide SEFE for two planar graphs where one graph has at most two cycles and the intersection is a pseudoforest in linear time. These results give rise to our hope that our SPQR-tree approach might eventually lead to a polynomial-time algorithm for deciding the general SEFE problem for two planar graphs.


Actions:
Download: [img] PDF - Preprinted Version
Download (221kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: [error in script] 12 (Google Scholar) | [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 12:26
    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 12:26
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/585