# zbMATH — the first resource for mathematics

From invariants to canonization in parallel. (English) Zbl 1142.68354
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 216-227 (2008).
Summary: A function $$f$$ of a graph is called a complete graph invariant if two given graphs $$G$$ and $$H$$ are isomorphic exactly when $$f(G) = f(H)$$. If additionally, $$f(G)$$ is a graph isomorphic to $$G$$, then $$f$$ is called a canonical form for graphs. Y. Gurevich [“From invariants to canonization”, Bull. EATCS 63, 115–119 (1997; Zbl 0886.68065)] proved that any polynomial-time computable complete invariant can be transformed into a polynomial-time computable canonical form. We extend this equivalence to the polylogarithmic-time model of parallel computation for classes of graphs having either bounded rigidity index or small separators. In particular, our results apply to three representative classes of graphs embeddable into a fixed surface, namely, to 3-connected graphs admitting either a polyhedral or a large-edge-width embedding as well as to all embeddable 5-connected graphs. Another application covers graphs with treewidth bounded by a constant $$k$$. Since for the latter class of graphs a complete invariant is computable in NC, it follows that graphs of bounded treewidth have a canonical form (and even a canonical labeling) computable in NC.
For the entire collection see [Zbl 1136.68005].

##### MSC:
 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science
Full Text: