An Efficient Genus Algorithm Based on Graph Rotations

This is joint work with Alexander Metzger. The question behind it is easy to state: given a graph, what is the fewest number of handles a surface needs so the graph can be drawn on it with no edges crossing? That number is the graph’s genus, and it is genuinely hard to compute — most algorithms get tangled up in where to route the “bridges.”

Our algorithm, PAGE (Practical Algorithm for Graph Embedding), gets around that by working directly with rotation systems. We built it to actually be usable: it is simple to implement, it hands back the faces of an optimal embedding, and it narrows the upper and lower bounds on the genus as it runs. We used it to determine genera that were not previously known — for instance, the $(3,12)$-cage turns out to have genus $17$.