  A function $f$ of a graph is called a complete graph invariant if the
isomorphism of graphs $G$ and $H$ is equivalent to the equality $f(G)=f(H)$.
If, in addition, $f(G)$ is a graph isomorphic to $G$, then $f$ is called a
canonical form for graphs. Gurevich proves that graphs have a polynomial-time
computable canonical form exactly when they have a polynomial-time computable
complete invariant. We extend this equivalence to the polylogarithmic-time
model of parallel computation for classes of graphs with bounded rigidity index
and for classes of graphs with small separators. In particular, our results
apply to three representative classes of graphs embeddable into a fixed
surface, namely, to 5-connected graphs, to 3-connected graphs admitting a
polyhedral embedding, and 3-connected graphs admitting a large-edge-width
embedding. Another application covers graphs with bounded treewidth. Since in
the latter case an NC complete-invariant algorithm is known, we conclude that
graphs of bounded treewidth have a canonical form (and even a canonical
labeling) computable in NC.
