Fowler, J. Joseph, Gutwenger, Carsten, Jünger, Michael, Mutzel, Petra ORCID: 0000-0001-7621-971X and Schulz, Michael (2009). An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges. In: Graph Drawing GD 2008, pp. 157-168. Springer-Verlag.
|
PDF
zaik2009-585.pdf - Submitted Version Download (221kB) | Preview |
Abstract
We present a linear-time algorithm for solving the simulta- neous embedding problem with ?xed 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.
Item Type: | Book Section, Proceedings Item or annotation in a legal commentary | ||||||||||||||||||||||||
Creators: |
|
||||||||||||||||||||||||
URN: | urn:nbn:de:hbz:38-549856 | ||||||||||||||||||||||||
Title of Book: | Graph Drawing GD 2008 | ||||||||||||||||||||||||
Series Name: | Lecture notes in computer science | ||||||||||||||||||||||||
Volume: | 5417 | ||||||||||||||||||||||||
Page Range: | pp. 157-168 | ||||||||||||||||||||||||
Date: | 2009 | ||||||||||||||||||||||||
Publisher: | Springer-Verlag | ||||||||||||||||||||||||
Language: | English | ||||||||||||||||||||||||
Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||||||||||||||||||
Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||||||||||||||||||
Subjects: | Data processing Computer science | ||||||||||||||||||||||||
Refereed: | No | ||||||||||||||||||||||||
URI: | http://kups.ub.uni-koeln.de/id/eprint/54985 |
Downloads
Downloads per month over past year
Export
Actions (login required)
View Item |