Locally maximal embeddings of graphs into surfaces (Seminar DM)

Iz MaFiRaWiki

Locally maximal embeddings of graphs into surfaces

Michal Kotrbčík, Comenius University, Bratislava, Slovakia

Torek, 26. oktober 2010, od 10-12, Plemljev seminar, Jadranska 19

A locally maximal embedding of a graph G is a cellular embedding of G on an orientable surface such that every vertex 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.

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja