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.
An embedding is a drawing of a graph on a surface where edges meet only at their intended endpoints. If the surface is a plane, the graph is planar. If the surface needs one handle, like a donut, the graph has genus 1; two handles means genus 2; and so on. The goal is to find the smallest surface that gives the graph enough room.
The thesis starts by building that intuition: topology, compact surfaces, graph embeddings, and rotation systems. A rotation system is a compact way to describe an embedding without drawing the whole surface. For each vertex, it records the cyclic order in which the incident edges appear as you walk around that vertex. Those local orders determine how the faces of the drawing fit together. Check out the interactive explanation here.
From exposition to algorithm
Once embeddings can be described combinatorially, they become searchable. PAGE takes advantage of the cycle sequence of a graph to search in the most efficient order. The thesis walks through the algorithm and its results, including the genus-17 computation for the (3,12)-cage. Check out an explanation here.
Why it matters
There are lots of reasons you might want to lay out a graph without crossings with as few holes as possible. For instance, in circuit design, the wire connections can be viewed as a graph, crossings are undesirable because they cause short-circuiting, and holes are costly because they require more layers in the printed circuit board. In infrastructure design, road networks form a graph, crossings are inefficient, and holes (i.e., bridges and tunnels) are costly.
Personally, I really 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. This combination really makes algorithmic mathematics feel alive. Not to mention, it is incredibly satisfying to optimize the algorithm for larger and larger graphs which yields more and more intricate visualizations.The demo below shows the same idea in miniature. You build a graph, PAGE searches for a low-genus embedding, and the drawing routine returns a polygon picture. When matching polygon sides are glued together, the picture represents a surface where the graph can be drawn without crossings. The rotation system is the text certificate of that drawing: each line says which neighbors surround a vertex and in what cyclic order.