zbMATH — the first resource for mathematics

On the cutting edge: simplified \(O(n)\) planarity by edge addition. (English) Zbl 1086.05067
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.

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