Report Number: CS-TR-71-192
Institution: Stanford University, Department of Computer Science
Title: An n log n algorithm for isomorphism of planar triply
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.