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 (216Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2009-585
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