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. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008 , pp. 157-168(Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_16).

Full text not available from this repository.

Abstract

We present a linear-time algorithm for solving the simultaneous 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 problem, 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-00219-9_16
Classifications: M Methods > M.600 Planar
G Algorithms and Complexity > G.490 Embeddings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/905

Actions (login required)

View Item View Item