Maximum genus - old problem and new results (Seminar DM)

Iz MaFiRaWiki

Maximum genus - old problem and new results.

Michal Kotrbčik


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


In this talk we discuss the problem of determining the maximum integer k such that a given graph has an embedding into the orientable surface of genus k. This integer is known as the maximum genus of a graph and can be characterised combinatorially, without referring to surfaces.

Using such characterisations, we derive four types of results. First, we present a new simple 2-approximation algorithm for the maximum genus.

Second, we investigate the matching number of the intersection graph of fundamental cycles with respect to different spanning trees of a graph.

Third, we show that the maximum genus can provide both lower and upper linear bound on the maximum number of pairwise vertex-disjoint cycles of a graph.

Finally, we show how one can easily obtain lower and upper bounds on the maximum genus of graphs from particular classes, for example, graphs with fixed girth and minimum degree.


Glej tudi/See also


Seminar za diskretno matematiko

Osebna orodja