Dans une première partie, nous considérons le problème du démêlage de graphes sur les surfaces : étant donné un dessin d’un graphe sur une surface, éventuellement avec des croisements, nous devons supprimer tous les croisements en déformant le dessin continuement, ou affirmer correctement que ce n’est pas possible. Nous donnons les premiers algorithmes en temps polynomial pour ce problème. Pour ce faire, nous introduisons un nouveau type de triangulations de surfaces qui discrétisent les surfaces à courbure négative d’une façon meilleure que l’état de l’art. Sur ces triangulations, nous fournissons un analogue combinatoire des célèbres plongements barycentriques de Tutte.
Dans un cadre plus géométrique, nous donnons un nouvel algorithme efficace pour calculer une triangulation de Delaunay d’une surface abstraite plate par morceaux (une généralisation des maillages). Nous étudions également l’algorithme classique de bascule de Delaunay et prouvons, lorsque la surface est un tore plat, la première borne dans le pire cas qui soit opti- male à facteur constant près. Sur les surfaces hyperboliques, nous fournissons une implémentation de l’algorithme de bascule de Delaunay, collectée dans un package de la bibliothèque standard de géométrie algorithmique CGAL, et accompagnée d’outils de génération et de visualisation pratiques.
ENGLISH VERSION:
In a first part, we consider the problem of untangling graphs on surfaces: given a drawing of a graph on a surface, possibly with crossings, remove all crossings by deforming the drawing continuously, or correctly assert that this is not possible. We give the first polynomial time algorithms for this problem. To do so we introduce a new kind of triangulations of surfaces that discretize negative-curvature surfaces in a better way than the state of the art. On these triangulations, we provide a combinatorial analog of the celebrated barycentric embeddings of Tutte.
In a more geometric setting, we give a new efficient algorithm for computing a Delaunay triangulation of an abstract piecewise-flat surface (a generalization of meshes). We also study the classical Delaunay flip algorithm, and prove, when the surface is a flat torus, the first worst-case bound that is tight up to a constant factor. On hyperbolic surfaces, we provide an implementation of the Delaunay flip algorithm, collected in a package of the standard library of computational geometry CGAL, along with convenient generation and visualization tools.
Localisation
Salle de réunion 4B172 (bâtiment Copernic)