An SPQRTree Approach to Decide Special Cases of Simultaneous Embedding with Fixed EdgesFowler, J. Joseph and Gutwenger, Carsten and Jünger, Michael and Mutzel, Petra and Schulz, Michael (2009) An SPQRTree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges. In: Graph Drawing 16th International Symposium, GD 2008, September 21 24, 2008 , pp. 157168(Official URL: http://dx.doi.org/10.1007/9783642002199_16). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642002199_16
AbstractWe present a lineartime algorithm for solving the simultaneous 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 problem, we present an algorithm that is based on SPQRtrees and has linear running time. We also show how we can employ SPQRtrees 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 SPQRtree approach might eventually lead to a polynomialtime algorithm for deciding the general SEFE problem for two planar graphs.
Actions (login required)
