An Efficient Genus Algorithm Based on Graph Rotations
For graph theorists and algorithm designers, this provides a practical genus algorithm with theoretical guarantees, though it is incremental over existing approaches.
The paper presents an algorithm to compute the orientable genus of any graph in O(n(4^m/n)^{n/t}) time, avoiding bridge placement issues, and demonstrates it on the (3,12) cage (genus 17).
We study the problem of determining the minimal genus of a simple finite connected graph. We present an algorithm which, for an arbitrary graph $G$ with $n$ vertices and $m$ edges, determines the orientable genus of $G$ in $O(n(4^m/n)^{n/t})$ steps where $t$ is the girth of $G$. This algorithm avoids difficulties that many other genus algorithms have with handling bridge placements which is a well-known issue. The algorithm has a number of useful properties for practical use: it is simple to implement, it outputs the faces of an optimal embedding, and it iteratively narrows both upper and lower bounds. We illustrate the algorithm by determining the genus of the $(3,12)$ cage (which is 17); other graphs are also considered.