Cutting triangulated surfaces and graphs of bounded genus.

Orateur: HUBARD Alfredo
Localisation: INRIA, France
Type: Groupe de travail analyse, probabilités et statistique
Site: UPEM
Salle: 3B082
Date de début: 26/05/2015 - 10:30
Date de fin: 26/05/2015 - 10:30

How much cutting is needed to simplify the topology of a surface? I will discuss bounds for several instances of this question that appeared in a joint work with Eric Colin de Verdière and Arnaud de Mesmay: for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces. These questions, come from the computational topology and topological graph theory literature, and much of the work that we did involved setting a simple way to translate analogous results from Riemannian systolic geometry. I will give proofs of this translation. Then I will talk about the separator theorem of Lipton and Tarjan that provides a bound on the Cheeger constant of any planar graph. It was in generalising this theorem to surfaces that computational topologists discovered discrete systolic geometry.