Clearly, the graph canonization problem is at least as computationally hard as the graph isomorphism problem.
For trees, a concise polynomial canonization algorithm requiring O(n) space is presented by [REF].