Working Seminar on Formal Models, Discrete Structures, and Algorithms

Locally-maximal embeddings of graphs into surfaces

Michal Kotrbčík (Comenius University)

When: October 14, 2pm

Where: room G2.91b/G215


For a fixed graph G, we consider the set of all (cellular) embeddings of G into (orientable) surfaces. Perhaps the two most classical question in the area are the determination the minimum and maximum genus of an embedding in this set; these numbers are known as the minimum, respectively the maximum genus of G. More generally, we are interested in the structure of the set of all embeddings of G. In the first part of the talk we give an overview of the essential concepts and results in the area.

Based on local changes of rotations, we introduce a natural greedy algorithm which finds a high-genus embedding. The possible outcomes of this algorithm are called locally-maximal embeddings. In the second part of the talk we discuss structural and algorithmical properties of locally-maximal embeddings and their relationship with other graph parameters such as minimum genus, maximum genus, and the cycle-packing number, that is, the maximum number of vertex-disjoint cycles of the graph. While there are two polynomial-time algorithm for the maximum genus, both are complicated and unsuitable for practical implementation. One particular outcome of our work are two novel and very simple greedy 2-approximation algorithms for the maximum genus.