One of the things that makes me very cool – aside from my etymological skills and ability to name all members past & present of Fleetwood Mac – is that I’m very good at optimising repetitive tasks in my day-to-day life. I can tell you’re impressed already.

There are easy tasks in life I apply this to daily: transposing my bartending skills to make a cup of tea and pour some juice at the same time; creating scripts to bypass any security or login screens; and writing on a website so that I don’t have to call multiple friends and tell them what I’m doing individually. However, not all challenges are this easy to solve, and one in particular can take many weeks of analysis before it is optimised.

Pre-boarding is a subset of the travelling problem space and involves being at just the right place to get on and off some form of transport at just the right time. In my case, this is on the New York City subway. There are many factors to consider, and the majority of these are temporal in nature. There are factors that can be solved with minimal trial and error, such as knowing where to stand on the platform, which door to board the train on, where to stand within the train, which staircases and exits to take and which parts of the journey are so noisy that you can blast Huey Lewis & The News in your headphones with no-one judging you.

However, before beginning this research, the initial problem is that of actually planning a route. Where locations are directly outside subway stops, or only near one particular line, this becomes easier, but in Manhattan, especially when walking is involved, there can be many options, and so a study of geometry and graph theory is needed.

The space we are all most familiar with is what is called Euclidean Space, and contains three continuous dimensions: x, y and z (or if you prefer: upwards, forwards and sideways). There also exist alternative spaces, one of the easiest of which to understand is taxicab geometry. I recommend Taxicab Geometry: An Adventure in Non-Euclidean Geometry if you’re interested, but in brief, this considers space as being represented by a grid structure. In the below, then, the green line is the Euclidean distance and route, and the purple line the Manhattan distance (or taxicab distance) and route. Many different taxicab routes would share the same minimum distance. Circles therefore become squares, spheres become cubes and accurate route-planning can be achieved in New York.

However, should we wish to compare the time taken between different subway stations, or to penalise parts of a walking route (e.g. walking through Times Square takes twice as long as any other street), then we have a pathfinding problem. Whilst these are often associated with artificial intelligence, they are in large part simply the application of graph theory, and often Dijkstra’s algorithm will provide the optimal solution.

Graph theory tells us to represent all of the points – be these cross-streets, subway stations or others – as verticies (or nodes) and to join them, where appropriate, with edges (or arcs). These edges may have a weight, for example, the time it takes to move between them. Below is a simple representation of part the London Underground as a weighted graph. As a bonus game for my British friends, I’ve removed most station names, see if you can complete them. In this very fake example, you can see that it’s actually quicker to go on two different lines to get from the blue to the pink dot, rather than take the direct route. When delays and weekend service come into play, however, examples like the below aren’t so far-fetched.

There are many types of graph, and many properties within them. A trail goes from one point to another without going along the same edge twice, a path is similar, but never visits the same point twice, and a cycle is a path that returns to its start point. I work with graphs daily, although my research is more to do with their semantics rather than their structure, so I actually deal very little with graph theory. Still, it’s a fascinating area with many challenges.

The seminal problem in graph theory was that of the Seven Bridges of Königsberg, which asks if there is any way to cross all the bridges in Königsberg exactly once on the same walk (without swimming). In 1735, Leonhard Euler proved this was impossible and in doing so laid the foundations of graph theory, and in 1944, frustrated maths students in the RAF rendered the problem void by blowing up a couple of the bridges.

Making such a journey is only possible where a Eulerian graph (a graph containing a Eulerian trail) can be made. If one can also return to one’s start point, then a Eulerian cycle exists. One of the major challenges in contemporary mathematics is finding someone other than Euler after whom to name things.

For those of you who’ve read this far, clicked all the links and ordered an Euler poster for your bedroom wall, I have, to finish, a less mathematical, but endlessly fun Flash game built on these concepts — Planarity, which challenges the player to separate a tangled graph into one where no two edges cross.

For those who skimmed to the end, however, please stop reading here. The kisses below aren’t for you.

Xx