Michal Kotrbčík:Locally maximal embeddings of graphs into surfaces

Povzetek.

A locally maximal embedding of a graph G is a cellularembedding of G on an orientable surface such that everyvertex of G is incident with at most two faces. These are precisely the embeddings whose genus cannot be raised by moving any edge in the local rotation at one of is end-vertices. The locally maximal genus of a graph G is the minimum genus of a locally maximal embedding of G. We investigate locally maximal embeddings of graphs, providing a method for constructing locally maximal embeddings with many faces (that is, with low genus). We show that the maximum number of vertex disjoint cycles of G is a tight upper bound on the maximum number of faces of any locally maximal embedding of G. By combining these two results we are able to calculate the locally maximal genus of many interesting classes of graphs, for example complete graphs, complete bipartite graphs and hypercubes. We investigate the relationships between locally maximal genus, minimum genus, and maximum genus. In particular, we provide results towards a classification of all graphs with locally maximal genus equal to minimum genus.

Joint work with M. Škoviera.