Sergio Cabello: Algoritmi za grafe na ploskvah

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.