Working Seminar on Formal Models, Discrete Structures, and Algorithms

Practical algorithms for minimum genus

Michal Kotrbčík (Masaryk University, Brno)

When: June 18, 2pm

Where: room C417


The minimum genus of a graph is the minimum genus of an orientable surface into which the graph can be embedded without crossings. In particutal, a graph has minimum genus zero if and only if it is planar. Low genus embeddings are useful in algorithm design, and the value of maximum genus of a specific graph/family of graphs is often interesting for mathematicans. However, the minimum genus problem is notoriously difficult from both theoretical and practical perspective. In this talk I will survey the multifold motivations to study minimum genus and indicate the involved difficulties. In the second part of the talk I will present our recent ILP and SAT formulations of the problem and evaluate their performance.

Joint work with Stephan Beyer, Markus Chimani and Ivo Hedtke.