Report Number: CS-TR-71-201
Institution: Stanford University, Department of Computer Science
Title: Planarity testing in V log V steps: extended abstract
Author: Hopcroft, John E.
Author: Tarjan, Robert Endre
Date: February 1971
Abstract: An efficient algorithm is presented for determining whether or not a given graph is planar. If V is the number of vertices in the graph, the algorithm requires time proportional to V log V and space proportional to V when run on a random-access computer. The algorithm constructs the facial boundaries of a planar representation without backup, using extensive list-processing features to speed computation. The theoretical time bound improves on that of previously published algorithms. Experimental evidence indicates that graphs with a few thousand edges can be tested within seconds.
http://i.stanford.edu/pub/cstr/reports/cs/tr/71/201/CS-TR-71-201.pdf