The thesis explains minimal-genus graph embedding and studies PAGE, a Practical Algorithm for Graph Embedding that uses cycle structure to work efficiently in practice.
Why surfaces enter the story
Graph theory often begins on paper: dots and lines. But many graphs are not really paper-friendly. They need a richer surface before their edges can avoid crossing. A torus, for example, gives K3,3 a path around the hole that a flat sheet cannot provide.
The thesis starts by building that intuition carefully: topology, compact surfaces, graph embeddings, and rotation systems. Rotation systems are especially delightful because they convert a geometric drawing question into combinatorial data about the order of edges around vertices.
From exposition to algorithm
Once embeddings can be described combinatorially, they become searchable. PAGE takes advantage of the cycle sequence of a graph, which is especially useful for graphs with high girth or low degree. The thesis walks through the algorithm and its results, including the genus-17 computation for the (3,12)-cage.
Why it matters
I like this project because it is both visual and computational. The pictures give you intuition; the rotation systems give you a certificate; the implementation gives you something you can run. That combination is exactly what makes algorithmic mathematics feel alive.