Graph canonization

In graph theory, a branch of mathematics, graph canonization is finding a canonical form of a graph G, which is a graph Canon(G) isomorphic to G such that Canon(H) = Canon(G) if and only if H is isomorphic to G. The canonical form of a graph is an example of a complete graph invariant. Since the vertex sets of (finite) graphs are commonly identified with the intervals of integers 1,..., n, where n is the number of the vertices of a graph, a canonical form of a graph is commonly called canonical labeling of a graph. Graph canonization is also sometimes known as graph canonicalization.

A commonly known canonical form is the lexicographically smallest graph within the isomorphism class, which is the graph of the class with lexicographically smallest adjacency matrix considered as a linear string.

Computational complexity

Clearly, the graph canonization problem is at least as computationally hard as the graph isomorphism problem. In fact, Graph Isomorphism is even AC⁰-reducible to Graph Canonization. However it is still an open question whether the two problems are polynomial time equivalent.

While existence of (deterministic) polynomial algorithms for Graph Isomorphism is still an open problem in the computational complexity theory, in 1977 Laszlo Babai reported that a simple vertex classification algorithm after only two refinement steps produces a canonical labeling of an n-vertex random graph with probability 1 − exp(−O(n)). Small modifications and added depth-first search step produce canonical labeling of all graphs in linear average time. This result sheds some light on the fact why many reported graph isomorphism algorithms behave well in practice. This was an important breakthrough in probabilistic complexity theory which became widely known in its manuscript form and which was still cited as an "unpublished manuscript" long after it was reported at a symposium.

The computation of the lexicographically smallest graph is NP-Hard.

For trees, a concise polynomial canonization algorithm requiring O(n) space is presented in. Begin by labeling each vertex with the string 01. Iteratively for each non-leaf x remove the leading 0 and trailing 1 from x's label; then sort x's label along with the labels of all adjacent leaves in lexicographic order. Concatenate these sorted labels, add back a leading 0 and trailing 1, make this the new label of x, and delete the adjacent leaves. If there are two vertices remaining, concatenate their labels in lexicographic order.

Applications

Graph canonization is the essence of many graph isomorphism algorithms.

A common application of graph canonization is in graphical data mining, in particular in chemical database applications.

A number of identifiers for chemical substances, such as SMILES and InChI, designed to provide a standard and human-readable way to encode molecular information and to facilitate the search for such information in databases and on the web, use canonization step in their computation, which is essentially the canonization of the graph which represents the molecule.

Example

An example of a canonical form associated with planar-graphs that is used in the study of graph-coloring is one where vertices associated with a planar graph is deformed into blocks and certain edges are represented as lines between such blocks.. This is done in such a way that the one-to-one correspondence between the planar graph being canonized and the canonical-form associated is preserved.

Canonical Form

References

• Yuri Gurevich, From Invariants to Canonization, The Bull. of Euro. Assoc. for Theor. Computer Sci., no. 63, 1997.[1]