On the cutting edge: simplified \(O(n)\) planarity by edge addition. (English) Zbl 1086.05067

Boyer, John M.; Myrvold, Wendy J.

J. Graph Algorithms Appl. 8, No. 3, 241-273 (2004).

Summary: We present new \(O(n)\)-time methods for planar embedding and Kuratowski subgraph isolation that were inspired by the Booth-Lueker PQ-tree implementation of the Lempel-Even-Cederbaum vertex addition method. In this paper, we improve upon our conference proceedings formulation and upon the Shih-Hsu PC-tree, both of which perform comprehensive tests of planarity conditions embedding the edges from a vertex to its descendants in a ‘batch’ vertex addition operation. These tests are simpler than but analogous to the templating scheme of the PQ-tree. Instead, we take the edge to be the fundamental unit of addition to the partial embedding while preserving planarity. This eliminates the batch planarity condition testing in favor of a few localized decisions of a path traversal process, and it exploits the fact that subgraphs can become biconnected by adding a single edge. Our method is presented using only graph constructs, but our definition of external activity, path traversal process and theoretical analysis of correctness can be applied to optimize the PC-tree as well.

MSC:

05C85	Graph algorithms (graph-theoretic aspects)
05C10	Planar graphs; geometric and topological aspects of graph theory
68P05	Data structures
68Q25	Analysis of algorithms and problem complexity

Keywords:

planar embedding; path traversal process