Session B2 - Graph Theory and Combinatorics
July 15, 17:00 ~ 17:50 - Room B7
Some topological algorithms for graphs on surfaces
Éric Colin de Verdière
Université Paris-Est Marne-la-Vallée and CNRS, France - firstname.lastname@example.org
The aim of this talk is to survey various recent results for solving computational problems for graphs on surfaces, at the interface of topological graph theory and graph algorithms.
Given a topologically non-trivial surface (up to homeomorphism, a sphere with handles), how can we compute a shortest non-contractible closed curve (which cannot be continuously deformed to a point)? How can we cut the surface economically to to make it planar (homeomorphic to a disk)? These are basic topological questions, which we revisit them from an algorithmic perspective.
Conversely, we will illustrate how topology can help devising more efficient graph algorithms in the case of graphs embeddable on a fixed surface, in the case of the minimum multicut problem.