19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

High-genus embeddings.

Presented by Michal KOTRBčíK
Type: Oral presentation
Track: Maps and Symmetries


In this talk we present a new class of embeddings of graphs into surfaces - locally maximal embeddings. An embedding is locally maximal if its genus cannot be raised by moving one end of an edge in the local rotation at the corresponding endvertex. The locally maximal genus of a graph is the minimum genus among its locally maximal embeddings. Locally maximal embeddings have many interesting structural properties and are strongly related to the structure of the embedding range of the graph in question. Among other results we present a lower bound on the locally maximal genus and several constructions of locally maximal embeddings. As a particular consequence we are able to compute the locally maximal genus of several graph classes such as complete and complete bipartite graphs. An alternative viewpoint on one of the constructions yields a very simple and fast polynomial-time approximation algorithm for the maximum genus: for an arbitrary connected graph $G$ the algorithm returns an integer $k$ such that $\gamma_M(G)/2 \le k \le \gamma_M(G)$.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors