# How can I produce 'canonical' forms for rooted bipartite graphs?

The graphs I'm interested in are bipartite graphs with a specified root vertex. Because there's a root, all the vertices are 'graded' by their distance from the root. Because the graph is bipartite, vertices at depth $d$ are only ever connected to other vertices at depths $d \pm 1$ (and in particular not depth $d$).

When I represent these graphs, I order the vertices at each depth, and record the edges by a series of matrices, essentially the list of adjacency matrices from each depth to the next. (That is, the full adjacency matrix is symmetric and block tridiagonal, with zero diagonal blocks. I just write down the superdiagonal blocks.)

Now, if I reorder the vertices at some depth (this just permutes the rows of one matrix and the columns of the next), obviously I have the same underlying graph. I'd like an algorithm that picks a particular ordering at each depth, for each such graph, producing a 'canonical form', with the following properties:

1. the algorithm is idempotent; applying it a second time does nothing,
2. the algorithm is stable, in the sense that if you just look at the first $d$ depths of a graph, and see that that graph is already 'in canonical form', then when you produce a canonical form for the whole graph those first $d$ depths aren't changed, and
3. as many isomorphic graphs as possible are identified!

It may not be possible to satisfy 3. completely; for example the identity operation satisfies 1. and 2., but does a very bad job at 3. It's not essential for my application that every isomorphic pair of graphs are identified. (I'd be using this algorithm to speed up a combinatorial search of certain types of graphs, where I know that I'm unnecessarily producing many isomorphic copies of the same graph, but the details of the search require that I use this representation.)

Does anyone know of such an algorithm? Can anyone suggest something good?

This problem is algorithmically equivalent to the general problem of finding a canonical labelling for a graph. To see that, take an arbitrary graph, add a new vertex adjacent to everything and call it the root, then subdivide every edge with a new vertex. The result is a rooted bipartite graph. Going back to the original is easy. Canonical labelling has unknown worst case complexity, though there are effective programs like nauty, bliss and Traces that can handle graphs with thousands of vertices.

I think that the best way to do is the following trivial algorithm. Whenever you want to order the vertices at depth d+1, look at the already ordered level d and associate with every vertex on level d+1 the string whose ith bit is 1 if it is connected to the ith vertex on level d and 0 if it is not. Then order the vertices on the d+1st level according to the lexicographic order of the strings, deciding equalities according to the original order of the vertices in the adjecency matrix (or any other way). I think it is clear that it is impossible to do any better if you insist on property 2, since in this algorithm we differentiate all the vertices that we can.

• This is in fact what I've been doing -- essentially it's the same as sorting the rows of the last matrix. In many of the examples I have, "deciding equalities" allows lots of scope for identifying more isomorphic graphs, but I never decided on a good criterion for sorting. Mar 2, 2010 at 17:34
• I am not sure what you mean by "deciding equalities" but for the question described above, I think this is the optimal solution as there is no way to differentiate between vertices that have the same neighbors on level d. Mar 2, 2010 at 21:08
• Sorry -- I was quoting your text when I said "deciding inequalities", and I meant what you did. Mar 3, 2010 at 0:52

You may find Mugnier and Chein's paper "Characterization and algorithmic recognition of canonical conceptual graphs" (1993) useful.

• The link to springerlink.com is broken, but the article can also be found at doi:10.1007/3-540-56979-0_16. Jun 5, 2022 at 12:22
• Thank you for updating the link. Jun 6, 2022 at 16:04

I don't know of any definite answer to your question, but one idea would be to sort each level by increasing degree ? that gets you a little closer (though not that much) to isomorphism

• It's certainly a start. Be careful, however, as this doesn't literally satisfy condition 2! When you add on an extra depth worth of vertices, the degrees of the vertices at the previous depth can change. You could sort by "incoming degree", that is, the number of edges connecting to vertices at the smaller depth. Mar 2, 2010 at 5:56
• that's a good modification. i forgot the stability issue. Mar 2, 2010 at 7:01