Recently, someone left my office at Newcastle University and a new person took their place, so we needed a new sign on our front door. I wanted to do something clever with it, but it needed to be instantly legible to lost supervisors trying to find their students.

My first thought was that since there are seven of us, something to do with the Fano plane would look good. Our names didn’t have enough of the right letters in the right places for it to work, though.

That got me thinking about the Levenshtein distance. The Levenshtein distance between two strings is a measure of how many changes you need to make to one to end up with the other. I wrote a Python script which calculated the distance between each pair of names:

This is equivalent to a complete weighted graph, so I got it to find a minimal spanning tree:

I then made it produce a GraphViz file,

which produced this image:

The sign on my office door