Institution: Stanford University, Department of Computer Science

Title: An n log n algorithm for isomorphism of planar triply connected graphs

Author: Hopcroft, John E.

Date: January 1971

Abstract: It is shown that the isomorphism problem for triply connected planar graphs can be reduced to the problem of minimizing states in a finite automaton. By making use of an n log n algorithm for minimizing the number of states in a finite automaton, an algorithm for determining whether two planar triply connected graphs are isomorphic is developed. The asymptotic growth rate of the algorithm grows as n log n where n is the number of vertices in the graph.

http://i.stanford.edu/pub/cstr/reports/cs/tr/71/192/CS-TR-71-192.pdf