1
$\begingroup$

I am trying to find a description for canonical form (labelling) for a graph. Specifically, how do we arrive at canonical form for a given graph?

$\endgroup$
  • 1
    $\begingroup$ Nobody knows how to do this efficiently in general. $\endgroup$ – Yuval Filmus Sep 7 '17 at 10:51
  • 1
    $\begingroup$ Have you read the Wikipedia article? $\endgroup$ – Yuval Filmus Sep 7 '17 at 11:02
  • $\begingroup$ Yes, it mentions lexicographically smallest graph. But it doesn't define exactly the term "lexicographically small". $\endgroup$ – mach Sep 7 '17 at 11:34
  • 1
    $\begingroup$ You go over all different orders for vertices, and choose the one which results in the lexicographically smallest representation. Note that there might be other ways to canonicalize graphs (in which the canonical form is not the lexicographically smallest representation). $\endgroup$ – Yuval Filmus Sep 7 '17 at 11:38
  • 1
    $\begingroup$ I just described such an algorithm. Of course, it's not very efficient. As I said in my first comment, nobody knows how to efficiently canonicalize graphs. If we could do it, we would have solved the graph isomorphism problem. $\endgroup$ – Yuval Filmus Sep 7 '17 at 11:52
4
$\begingroup$

Graph canonization is a a procedure that takes a graph $G$ and returns an isomorphic graph $C(G)$, we the promise that $C(G) = C(H)$ iff $G$ and $H$ are isomorphic. We call $C$ a canonical form.

One possible canonical form is the lexicographically smallest adjacency matrix. Given an ordering of the vertices, we can serialize the adjacency matrix as a binary string. Given a graph $G$, we choose the ordering leading to the lexicographically smallest such string, and then order the graph accordingly to form $C(G)$. It is not hard to check that this is a canonical form.

The algorithm, as stated, has exponential complexity, so isn't practical. There might be faster ways to compute this canonical form, or they might be other canonical forms which are easier to compute. Notice, however, that canonical forms can be used to solve graph isomorphism, and so finding an efficiently computable canonical form is hard and might be impossible (depending on the meaning of efficient).

It is still possible that there is an easily computable canonical form that works for most graphs, just like graph isomorphism is easy for most graphs. For more on this topic, see this question, and particularly the survey by McKay and Piperno mentioned in my answer there.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.