Planarity Algorithms via PQ-Trees (Extended Abstract)

Bernhard Haeupler, Robert Endre Tarjan

Research output: Contribution to journalArticle

11 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)143-149
Number of pages7
JournalElectronic Notes in Discrete Mathematics
Volume31
Issue numberC
DOIs
StatePublished - Aug 20 2008

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Planarity Algorithms via PQ-Trees (Extended Abstract)'. Together they form a unique fingerprint.

  • Cite this