TABLE OF CONTENTS There are many practical situations in which one may wish to examine whether a given graph is planar, and if so, to find a planar embedding of the graph. For example, in the layout of printed or VLSI circuits, one is interested in knowing whether a graph G representing a circuit is planar and also in finding a planar embedding of G if it is planar. In this appendix we present a linear algorithm for the problem, due to [LEC67, BL76, CNAO85].
There are two typical algorithms which test planarity in linear time: one by Hopcroft and Tarjan [HT74], and the other by Booth and Lueker [BL76]. We present the latter called the vertex addition algorithm in Section A.2, because it is conceptually simpler than the former. The vertex addition algorithm was first presented by Lempel et al. [LEC67], and later improved to a linear algorithm by Booth and Lueker [BL76] employing an st-numbering algorithm and a data structure called a PQ-tree. The algorithm adds one vertex in each step. Previously embedded edges incident on this vertex are connected to it, and new edges incident on it are embedded and their ends are left unconnected. Sometimes whole pieces have to be reversed (flipped) around or permuted so that some ends occupy consecutive positions. If the representation of the embedded subgraph is updated with each alternation of the embedding, then the final representation will be an actual embedding of a given whole...
