Paper detail

From Invariants to Canonization in Parallel

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.