Our algorithm determines the orientable genus of a graph, outputs an optimal embedding, and proved that the previously stubborn (3,12)-cage has genus 17.
The puzzle
Imagine trying to connect three houses to three utilities without any pipes crossing. On a flat sheet, the classic utility graph K3,3 cannot be drawn cleanly. On a donut-shaped surface, it can. That one hole changes what is possible.
The genus of a graph is the smallest number of holes needed in a surface so the graph can be drawn without crossings. This is a beautiful mathematical invariant, but it also connects to circuit layout, network design, visualization, and other settings where crossings are costly or meaningful.
The algorithmic trick
Instead of trying every drawing directly, the algorithm works with rotations: the cyclic order of edges around each vertex. Those local choices determine the faces of a surface embedding. A naive algorithm would just iterate through the combinations of rotations around each vertex. However the large branching factor quickly becomes intractable even for graphs as small as the complete graph on 8 vertices. An improvement by Gunnar Brinkmann uses branch and bound to prune branches that can easily be deduced to yield higher genus than the current lowest branch. Yet this approach still has to explore many branches before the current best is good enough to prune all sub-optimal branches. Our algorithm instead looks at the faces of the 3D surface and notes that they can all be broken into cycles in the graph. Due to a result by Euler, it turns out that maximizing the number of faces is the same as minimizing the genus. By working with cycles, this then yields a practical way to iterate through the rotation systems in a heuristic order of minimal to maximal genus. As a result, our algorithm (PAGE) is orders of magnitude faster than prior algorithms in practice and can compute graphs with thousands of vertices and edges.
Why it matters
Having a practical algorithm is incredibly useful for both theoretical and applied use cases. It allows theoretical mathematicians to quickly validate hypotheses and spot patterns and it means that applied scientists can get useful results for most applications even though the problem is technically NP-hard.
Interactive Demo
Try the utility problem
Connect every utility to every house. Draw from a utility to a house with your mouse or finger, then validate the drawing to see missing connections and crossings.
Draw nine utility-to-house lines.