My lack of recent activity was owing to a boat club trip to Seville, with lots of sun, rowing and walking, but little internet access. However, now I am back, and during the trip the following curious pseudo-problem was posed.

Many Cambridge college boat clubs keep track of pairs of their members who have had romantic liasons (precise definitions of which vary from club to club but “sexual kissing” seems to be the standard benchmark), and so build up what are known as incest charts, which are essentially graphs where each member is a vertex and two people are joined by an edge if they have engaged one another in acts of ‘incest’.

First and Third had plans to put an anonymous (the vertices are left unnamed) incest chart on their website, but given the great size of the club, the actual generation of the graphic creates an interesting problem which isn’t exactly mathematical but clearly requires some kind of algorithmic mathematical handling.

Problem: Given a graph, expressed as a set of edges (any vertices of degree zero are ignored), find an algorithm for generating a graphical representation of the graph which is maximally intelligible to someone viewing the website. In particular, edges should cross as infrequently as possible and edges should be short and ideally straight.

This is a problem familiar to anyone who has done graph theory. You get half way through a diagram and then end up having to include lots of loopy things to make your graph make sense. It seems, to the author, a difficult task. If anyone has any ideas or knows of such an algorithm already, I would be interested to hear.

Advertisements