A Simple Test for Planar Graphs

[[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 graph-reduction technique is adopted so that the embeddings for the planar biconnected components constructed at each iteration never have to be changed.[[fileno]]2030218030059[[department]]資訊工程學