A new planarity test

Given an undirected graph, the planarity testing problem is to determine wh ether the graph can be drawn in a plane without any crossing edges. Linear time planarity testing algorithms have previously been designed by Hopcroft and Tarjan, and by Booth and Lueker. However, their approaches are quite i nvolved. Several other approaches have also been developed for simplifying the planarity test. In this paper, we developed a very simple linear time t esting algorithm based only on a depth-first search tree. When the given gr aph is not planar, our algorithm immediately produces explicit Kuratowski's subgraphs. A new data structure, PC-trees, is introduced, which can be vie wed as abstract subembeddings of actual planar embeddings. A graph-reductio n technique is adopted so that the embeddings for The planar biconnected co mponents constructed at each iteration never have to be changed. The recogn ition and embedding are actually done simultaneously in our algorithm (Boot h and Lueker, 1976). The implementation of our algorithm is quite straightf orward. (C) 1999 Published by Elsevier Science B.V. All rights reserved.