# A map of the mist

As a mathematician who dabbles in graph theory, I couldn't help but try and impose some order upon the tangled web of writeups in the mist. raincomplex's writeup above provides a schematic of the nodes and the links between them, but to do so without a messy overlap of joining lines each author appears several times. My first thought, then, was whether I could do better, and arrange the nodes into a map of the mist such that no paths crossed.

I couldn't. But I don't feel too bad about that, since no one else can either! Feeding a matrix representation of the graph into a suitable computer algebra system confirmed that it's non-planar: drawing it on a 2-d plane inevitably requires crossings. There will be a more exotic surface upon which it could be drawn in this way (there are non-planar graphs which can be arranged on a torus without crossings, for instance), but to do so requires determination of what's known as the genus of the graph, which (roughly speaking) indicates how many holes would be in this surface. However, after an hour of traumatising my Macbook's cooling fans the program hadn't found an answer, so this will remain a mystery of the mist for now.

Besides, the purpose of a map is to help find your way, and perhaps there I could do better: is it possible to visit each writeup once, but only once, such that each is connected to the next by one of the links in the graph? Such a journey is called a Hamiltonian path; if it's possible to return to the starting point from the last stop, then the loop is a Hamiltonian cycle. This tour problem lies somewhere between two rather more famous ones: The Bridges of Königsberg (where every edge is to be visited once and once only, rather than every node) and that of the Travelling Salesman (which introduces a cost of movement). In general, finding Hamiltonian paths or cycles is a hard challenge; it falls into the class of NP-complete problems, and there's a million dollars up for grabs for anyone who can demonstrate an efficient solution to those (or, like our non-planarity result earlier, prove that it's impossible to do so).

But raincomplex's map already provides a path through two thirds of the mist, and with a bit of fiddling I was able to fashion this into a Hamiltonian cycle. So if you'd like to explore the writeups without missing any, nor repeating yourself, here's a possible tour:

voices - breathe - tired - freedom - blood - curled - link-boys - trapped - resist - shadows - find - flow - halos - voices

Although of course, you may find many more.

**Bonus: Directed tours?**

It was pointed out to me that the tour above requires moving 'backwards' at some nodes. Forming the directed graph based on the possible exits from each writeup, there's a discrepency with *breathe*: only *voices* explicity links to it, despite it mentioning four potential entry points! I claim that as a result of this, there are only two possible directed Hamiltonian paths, neither of which is a cycle. As *voices* must lead to *breathe*, it cannot lead to *freedom*, which must therefore be linked to by *tired*, and so on: this builds up a series of rules for a Hamiltonian path which can be satisfied only by

* shadows → resist → find → flow → halos → voices → breathe → tired → freedom → blood → curled → link-boys → trapped*

or

*link-boys → trapped → halos → voices → breathe → blood → curled → flow → tired → freedom → shadows → resist → find*

But the situation is likely different if you consider entries rather than exits, or some combination of the two.