Last month I asked for recommendations for graph layout tools.

[simontatham@hachyderm.io]

Last month I asked for recommendations for graph layout tools. Thanks to everyone who suggested something! I've now finished the task I wanted them for, so have some pretty (ish) pictures.

In the end, I didn't use anything more complicated than Dotty, and I didn't even use Dotty on the _full_ version of either of my graphs. I was able to condense each graph to a simpler one by merging sets of vertices that had some semantic properties in common; then I used Dotty to lay out _those_ graphs (essentially using it like Untangle, but easier to remember which vertex was which), and then I did the manual layout of the full graph by re-expanding each vertex into a cluster of nearby ones and moving things about until everything fitted. So in the final layout, related vertices are grouped together, which shows something of the structure of each diagram.

That wasn't at all what I'd _expected_ to do. I had hoped to illustrate the relations between vertices by giving the whole graph symmetry, so that related vertices were images of each other in two reflective axes, or something similar. Clustering the related things together was a fallback option after that didn't go anywhere. But I think it ended up legible.

Just to show the difference, the third image in this post is essentially the same state machine as the second image – both are finite-state transducers for the Penrose P2 tiling using Robinson triangles. But the third image is how Graphviz laid it out when I let it do the whole job itself, for my 2024 blog post. However complicated you find my new hand-drawn version, I hope you'll at least agree that it's clearer than that!

[simontatham@hachyderm.io]

@spacehobo I'm afraid I didn't find the clusters by any automated procedure. I found them by knowing something about how I'd generated those graphs in the first place. I don't know of any software that would look for clusters of that kind automatically. It's an interesting thought, though!

In the first of my graphs here, the clusters are equivalence classes under two types of symmetry. The input to the state machine represents a pair of strings zipped together, symbolically describing adjacent tiles in a tiling (or rather, the machine tests _whether_ they could be adjacent). So the machine ought to be symmetric in swapping the two input strings. Also the symbols A,B,U,V represent the triangles you get by dividing Penrose kite and dart tiles in half along their line of symmetry, so there's a second symmetry in exchanging A↔B and U↔V. That gives natural groups of four vertices, except when things are fixed points of one or other transformation, or the two symmetries coincide.

In the second graph, there's only one input string, so I lost one of those symmetries – you can still exchange A↔B and U↔V, but you can't swap the inputs any more. But the second graph is the determinisation of the first, so each state corresponds to a set of states of the original graph, and I clustered states corresponding to the same set.