Planarity Algorithms via PQ-Trees (Extended Abstract)

We give an abstract vertex-addition method for planarity testing that encompasses the algorithms of Lempel, Even, and Cederbaum, Shih and Hsu, and Boyer and Myrvold. The main difference between the former and the latter two is the order of vertex addition; the latter two differ only in implementation details. For the general method we give a direct proof of correctness that avoids the use of Kuratowski's theorem. We give a linear-time implementation that simplifies and unifies the Shih-Hsu and Boyer-Myrvold methods. Our algorithm extends to generate embeddings uniformly at random, to count embeddings, to represent all embeddings, and to produce a Kuratowski subgraph of a non-planar graph. Our algorithm keeps track of all possible embeddings by reinterpreting Booth and Lueker's PQ-tree data structure to represent circular instead of linear orders. This interpretation of PQ-trees gives the PC-trees of Shih and Hsu and leads to a simpler, more-symmetric form of PQ-tree reduction.