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. By using cycle structure, the search can narrow upper and lower bounds and avoid some bridge-placement headaches that make genus algorithms difficult in practice.
The result is practical in a very satisfying sense: it is relatively simple to implement, it returns a certificate that can be checked, and it can produce the actual faces of the optimal embedding rather than only a number.
Why it matters
Computing the genus of the (3,12)-cage as 17 is the kind of result that makes a theoretical algorithm feel tangible. It says: here is a graph whose surface was hard to pin down, and here is a concrete way to certify it.