Two Different Ways to Handle Disconnected Graphs when Generating Graphs with Signatures

Disconnected graphs were mentioned in this post on OMG's algorithm. I also said that signatures could not handle such graphs, but this is not totally true. Here are a couple of approaches to handle them.

Firstly, why is this a problem at all? Well, a signature of a graph is a bit like a spanning tree - and the canonical signature is the maximal string form of the set of trees. However, for disconnected graphs you get a spanning forest - which is just a set of spanning trees. The maximum tree from the forest will no longer span the whole graph.


The image shows an example of this for a very simple graph. The upper panel shows a disconnected graph and its corresponding forest. The lower panel shows two different labelings of the same graph (A, B) and their canonical form. The algorithm for canonicalization simply has to 'paste' together canonical labels or signature strings, and has to make sure that a canonical signature is generated for each component. The components are ordered by their canonical strings.

An alternative solution to the problem for generating graphs is mentioned in a blog post by Derrick Stolee. Simply choose the canonical deleted edge to be one that will not disconnect the graph. For example, with an edge-addition canonical path algorithm, any edge that is a bridge (as discussed yesterday) would disconnect the graph if deleted. So the canonical edge is no longer the last edge in the canonically labelled graph but the last non-bridge edge.

Comments