Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00091
On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
Vol. 8, no. 3, pp. 241-273, 2004. Regular paper.
Abstract 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.
|
Journal Supporters
|