Report Number: CS-TR-71-192
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.