Canonical labeling of graphs

Abstract

We announce an algebraic approach to the problem of assigning canonical forms to graphs. We compute canonical forms and the associated canonical labelings (or renumberings) in polynomial time for graphs of bounded valence, in moderately exponential, exp(n½ + ο(1)),time for general graphs, in subexponential, nlog n, time for tournaments and for 2-(ν,κ,λ) block designs with κ,λ bounded and nlog log n time for λ-planes (symmetric designs) with λ bounded. We prove some related problems NP-hard and indicate some open problems.