Conference abstracts

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   -

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.

View abstract PDF

FoCM 2017, based on a nodethirtythree design.