Testing and Verifying Planarity and Non-Planarity in Graphs

Abstract

This paper presents an efficient planarity test for arbitrary undirected graphs. The algorithm is a restructured and slightly modified version of the one presented by Hopcroft and Tarjan which runs in O(n) time and space where n is the number of vertices. Various data structures specific to the algorithm are used to simplify reasoning of correctness and run time. In addition this paper outlines how to extract justification for the answer given by the algorithm, either with an embedding of the graph if the graph is planar or a Kuratowski subgraph if the graph is non-planar. This extraction process also takes linear time and space.