ABSTRACT

A planar graph is one which can be drawn on the plane without any crossing edge. Given an undirected graph G, the planarity test is to determine whether there exists a clockwise edge ordering around each vertex, such that the graph G can be drawn on the plane without any crossing edge. Linear-time planarity test was first established by Hopcroft and Tarjan [1] based on a path addition approach. The vertex addition approach, originally developed by Lempel et al. [2], was later improved by Booth and Lueker [3] (hereafter, referred to as B&L) to run in linear time using a data structure called PQ-tree. Several other approaches have also been developed for simplifying the planarity test (see e.g., [4-8]) and the embedding algorithm [9,10]. Shih and Hsu [11] (hereafter referred to as S&H) developed a linear-time test based on PC-trees (a generalization of P-trees), which did not use any template. In fact, based on this idea, Hsu [12] and Hsu and McConnell [13] further eliminated the template operations of the original PQ-tree for the consecutive ones test, and used PC-tree for the circular ones test directly. An earlier version [14] of Shih and Hsu [8] has been referred to as the simplest linear-time planarity test by Thomas in his lecture notes [15]. In this chapter we shall describe a PC-tree-based planarity test, which is much simpler than any previous version (c.f. [16]) of S&H. A software for our planarity test is available at https://github.com/x1213/planarityalgorithms/ in GitHub.