Abstract
Given an undirected graph, the planarity testing problem is to determine whether the graph can be drawn in the 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 involved. We develop a very simple linear time testing algorithm based only on a depth-first search tree. Our algorithm uses Kuratowski's theorem very explicitly. A graphreduction technique is adopted so that the embeddings for the planar biconnected components constructed at each iteration never have to be changed.