COMP 122: Algorithms and Analysis Testing Graph Planarity (Part 1 of 2)

Introduction In these two lectures, we will discuss the algorithm developed by Hopcroft and Tarjan [6] for efficiently testing whether a graph G = (V; E) is planar. This is an extremely elegant algorithm that runs in O(V) time, and brings together a number of algorithms and data structures that we have seen previously in class: radix sort, depth first search, biconnected components, and stacks. As I mentioned on the first day of class, the graph planarity problem has practical applications, e.g., in deciding whether a given electrical circuit can be laid out on a printed circuit board. While the Hopcroft-Tarjan algorithm is complex, it is a "classic in computational graph theory" and "a superb example of the design of an efficient graph algorithm" [1]. We are studying this algorithm precisely for this reason. I am aware of two textbooks [3, 7] that describe the algorithm. The problem of graph pla