TR-IIS-03-015    PDF format

Abstract

In Shih & Hsu [9] a simpler planarity test was introduced utilizing a data structure called PC-trees (general-ized from PQ-trees). In this paper we give an efficient implementation of that linear time algorithm and illus-trate in detail how to obtain a Kuratowski subgraph when the given graph is not planar, and how to obtain the embedding alongside the testing algorithm. We have implemented the algorithm using LEDA and an object code is available at http://qa.iis.sinica.edu.tw/graphtheory/. The main part of the implementation is devoted to the treatment of the C-nodes that represent those 2-connected components.

Keywords: algorithm, planar graphs, Kuratowski subgraph, PQ-tree, PC-tree, embedding