Geodesic
On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
Journal of Graph Algorithms and Applications, Tome 8 (2004) no. 3, pp. 241-273.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2004_8_3_a0,
     author = {John Boyer and Wendy Myrvold},
     title = {On the {Cutting} {Edge:} {Simplified} {O(n)} {Planarity} by {Edge} {Addition}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {241--273},
     publisher = {mathdoc},
     volume = {8},
     number = {3},
     year = {2004},
     doi = {10.7155/jgaa.00091},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00091/}
}
TY  - JOUR
AU  - John Boyer
AU  - Wendy Myrvold
TI  - On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
JO  - Journal of Graph Algorithms and Applications
PY  - 2004
SP  - 241
EP  - 273
VL  - 8
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00091/
DO  - 10.7155/jgaa.00091
LA  - en
ID  - JGAA_2004_8_3_a0
ER  - 
%0 Journal Article
%A John Boyer
%A Wendy Myrvold
%T On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
%J Journal of Graph Algorithms and Applications
%D 2004
%P 241-273
%V 8
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00091/
%R 10.7155/jgaa.00091
%G en
%F JGAA_2004_8_3_a0
John Boyer; Wendy Myrvold. On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, Tome 8 (2004) no. 3, pp. 241-273. doi : 10.7155/jgaa.00091. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00091/

Cité par Sources :