GAG 2019

Calculating the minimum genus of a graph


The minimum genus of a graph is the minimum genus of a surface in which the graph can be embedded.

 

Calculating the minimum genus of a graph can be a challenging computational problem. In recent work we use group theory and linear programming in new algorithms for calculating the minimum genus of a graph, and also, for constructing embeddings of a graph.

 

We show that these methods are useful in practice by calculating the minimum genus of several interesting graphs for which the minimum genus was not yet known.

 

This is joint work with Marston Conder.