Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
Charles J. Colbourn, Kellogg S. Booth · SIAM Journal on Computing · 1981
An algorithm based upon Edmonds’s procedure for testing isomorphism of trees is extended to answer various questions concerning automorphisms of a labeled forest. This and linear pattern matching techniques are used to build efficient algorithms which find the automorphism partition and a set of generators for the automorphism group, determine the order of the automorphism group, and compute a coding for forests, interval graphs, outerplanar graphs, and planar graphs.