"An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges"
Article by J. Joseph Fowler, Carsten Gutwenger, Michael Jünger, Petra Mutzel, Michael Schulz, available as BibTeX Source and in portable document format.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2009-585
Keywords:	Simultaneous Geometric Graph Embeddings
MSC codes:	05C10
This article was published in 2009 by Springer-Verlag in the proceedings "Graph Drawing GD 2008 Crete" (edited by I.G. Tollis and P. Patrignani), volume 5417, pages 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.