Home > News > Sergio Cabello: Algoritmi za grafe na ploskvah

Sergio Cabello: Algoritmi za grafe na ploskvah

Date: 24. 10. 2016
Source: Discrete mathematics seminar
Torek, 25. 10. 2016, od 10h do 12h, Plemljev seminar, Jadranska 19

Ob izvolitvi v naziv rednega profesorja bo imel dr. Sergio Cabello Justo javno predavanje z naslovom Algoritmi za grafe na ploskvah.

Povzetek. 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.