Interactions between algorithms, geometry and topology in low dimensions
Arnaud de Mesmay · HAL (Le Centre pour la Communication Scientifique Directe) · 2022
This habilitation thesis presents an overview of my research activities since the defense of my PhD Thesis. The common theme underlying most of my work is the investigation of the interactions between the algorithmic, geometric and topological properties of a mathematical object. The focus is on low dimensions: graphs and their embeddings on surfaces, as well as knots and 3-dimensional topology.This document showcases three lines of work that I have developed with multiple co-authors over the course of several years. The first one deals with a problem of surface decomposition: what is the best way to cut a surface into a disk? By duality, this problem is related to the algorithmic problem M ULTICUT for embedded graphs, asking for the best way to cut a graph so as to separate a specified set of pairs of terminals. We leverage topological algorithms to provide approximation schemes for both problems, and dually we develop new tools to establish lower bounds for computational problems involving embedded graphs, including these two. We then turn our attention towards the problem of computingoptimal homotopies, i.e., homotopies where the length of the longest curve is minimized. Their study is motivated by questions coming both from Riemannian and computational geometry. We prove strong results on the structure of optimal homotopies, valid in both the discrete and the continuous setting, and leverage those to provide improved algorithms to compute optimal homotopies exactly or approximatively, as well as to draw connections with graph minor theory. In a third step, we present a family of computational hardness results for various problems in knot theory and 3-dimensional topology. Most importantly we prove the NP-hardness for the problem of deciding embeddability of simplicial complexes in R3 and for the problem of optimally untangling a diagram of the unknot. We then survey more succinctly some other contributions pertaining to shortest path embeddings of graphs on surfaces, curve tightening and electrical transformations, treewidth of knot diagrams and the crossing number of links. We conclude with some perspectives and future research directions.