With Alexander Metzger, I present PAGE, a Practical Algorithm for Graph Embedding, which determines the orientable genus of an arbitrary connected graph. The algorithm works directly with rotation systems, where at each vertex you record the cyclic (clockwise) order of its incident edges, and that combinatorial data alone encodes an embedding.
From a rotation system you trace out facial walks, and by Euler's formula the minimum genus is attained exactly when the rotation system produces the most faces, so PAGE searches for that rotation system, narrowing both the upper and lower bounds as it runs. It is simple to implement, outputs the faces of the optimal embedding, and avoids the difficulties that many other genus algorithms have with handling bridge placements. We used PAGE to settle genera that were previously unknown, most notably the (3,12)-cage, which turns out to have genus 17, and to give the first bounds for graphs still out of reach. The implementation is available under an MIT license.
The full paper can be found here.