Normal forms for trivalent graphs and graphs of bounded valence

Abstract

A function f is defined, mapping graphs with n vertices onto graphs with vertex set {1,...,n} . f(X) is isomorphic to X and X is isomorphic to Y iff f(X) = f(Y). For each d, the restriction of f to graphs of valence d is computable in time O(nτ(d)) for a suitable integer τ(d).