An n LOG n Algorithm for Isomorphism of Planar Triply Connected Graphs

摘要

It is shown that the isomorphism problem for triply connected planar graphs, can be reduced to the problem of minimizing states in a finite automation. By making use of an n log n algorithm for minimizing the number of states in a finite automaton, an algorithm for determing 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. (Author)