Canonical labeling of graphs

1983/01/01 by László Babai, Eugene M. Luks · 415 citations
Engineering · Mathematics · Computer Science · #graph theory and CDMA systems #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems #Bounded function #Combinatorics #Mathematics #Algebraic number #Exponential function #Canonical form #Discrete mathematics #Time complexity #Block (permutation group theory) #Pure mathematics

paper · pdf · doi:10.1145/800061.808746

openalex publication_date 1983/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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.

Citations

• Isomorphism of graphs of bounded valence can be tested in polynomial time
• A note on the graph isomorphism counting problem
• Isomorphism testing for graphs of bounded genus
• A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• Finite Permutation Groups and Finite Simple Groups

Cited by

• The NP-completeness column
• Planar Graph Isomorphism is in Log-Space
• Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time
• Isomorphism testing and canonical forms for k-contractable graphs (A generalization of bounded valence and bounded genus)
• Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction
• Isomorphisms, Symmetry and Computations in Algebraic Graph Theory
• Two-closures of supersolvable permutation groups in polynomial time
• The Space Complexity of k-Tree Isomorphism
• A Logspace Algorithm for Partial 2-Tree Canonization
• Graph canonization [wikipedia]
• Graph isomorphism problem [wikipedia]