Algoritmi za grafe na ploskvah (Seminar DM)

Iz MaFiRaWiki

Algoritmi za grafe na ploskvah

Sergio Cabello

Torek, 25. oktober 2016, od 10h do 12h, Plemljev seminar, Jadranska 19


Graphs embedded on surfaces are a natural generalization of plane graphs. Any cycle in an embedded graph defines a closed curve in the surface and we can therefore consider topological properties of such a curve. When the graph is equipped with edge-weights, we can also talk about the length of cycles. We will give an overview of the algorithms and techniques used to find shortest cycles with certain topological properties in embedded graphs, like for example a shortest non-contractible cycle.

Seminar za diskretno matematiko

Osebna orodja