High-genus embeddings of graphs into surfaces

The maximum genus of a graph $G$ is the largest integer $k$ such that $G$ has a cellular embedding into the orientable surface of genus $k$. In the first part of the talk we focus on known properties and methods of construction of maximum-genus embeddings. In the second part of the talk we deal with embeddings with high genus. We present a simple greedy approximation algorithm for the maximum genus and show how it can be used to construct embeddings with genus less than maximum genus. Furthermore, we introduce locally maximal embeddings, a generalization of maximum-genus embeddings that provides some insight into
the structure of embeddings with high genus.

This is a joint work with M. Škoviera.