Auteur : Vincent DESPRE
Directeur de thèse : Andras SEBO
Co directeur : Françis LAZARUS
Date : 18 ocotbre 2016
Dans cette thèse, nous nous intéressons aux propriétés topologiques des surfaces, i.e. celles qui sont préservées par des déformations continues. Intuitivement, ces propriétés peuvent être imaginées comme étant celles qui décrivent la forme générale des surfaces. Nous utilisons des cartes combinatoires pour décrire les surfaces. Elles ont le double avantage d'être des objets mathématiques naturels et de pouvoir être transformées directement en structure de données.
Nous étudions trois problèmes différents. Premièrement, nous donnons des algorithmes de calcul du nombre géométrique d'intersection de courbes dessinées sur des surfaces. Nous avons obtenu: un algorithme quadratique de calcul du nombre minimal d'auto-intersections dans une classe d'homotopie, un algorithme quartique pour construire un représentant minimal et un algorithme quasi-linéaire pour déterminer si une classe d'homotopie contient bien une courbe simple. Nous donnons ensuite des contre-exemples à la conjecture de Mohar et Thomassen traitant de l'existence de cycles de partage dans les triangulations. Finalement, nous utilisons les travaux récents de Lévèque et Gonçalves à propos des bois toriques de Schnyder pour construire une bijection entre les triangulations du tore et certaines cartes unicellulaires analogues à la célèbre bijection de Poulalhon et Schaeffer pour les triangulations planaires.
Plusieurs points de vue sont utilisés au cours de cette thèse. Nous proposons donc un important chapitre préliminaire où nous insistons sur les connections entre ces différents points de vue.
Directeur de thèse : Andras SEBO
Co directeur : Françis LAZARUS
Date : 18 ocotbre 2016
Algorithmes pour la topologie, cas des graphes plongés sur des surfaces.
Dans cette thèse, nous nous intéressons aux propriétés topologiques des surfaces, i.e. celles qui sont préservées par des déformations continues. Intuitivement, ces propriétés peuvent être imaginées comme étant celles qui décrivent la forme générale des surfaces. Nous utilisons des cartes combinatoires pour décrire les surfaces. Elles ont le double avantage d'être des objets mathématiques naturels et de pouvoir être transformées directement en structure de données.
Nous étudions trois problèmes différents. Premièrement, nous donnons des algorithmes de calcul du nombre géométrique d'intersection de courbes dessinées sur des surfaces. Nous avons obtenu: un algorithme quadratique de calcul du nombre minimal d'auto-intersections dans une classe d'homotopie, un algorithme quartique pour construire un représentant minimal et un algorithme quasi-linéaire pour déterminer si une classe d'homotopie contient bien une courbe simple. Nous donnons ensuite des contre-exemples à la conjecture de Mohar et Thomassen traitant de l'existence de cycles de partage dans les triangulations. Finalement, nous utilisons les travaux récents de Lévèque et Gonçalves à propos des bois toriques de Schnyder pour construire une bijection entre les triangulations du tore et certaines cartes unicellulaires analogues à la célèbre bijection de Poulalhon et Schaeffer pour les triangulations planaires.
Plusieurs points de vue sont utilisés au cours de cette thèse. Nous proposons donc un important chapitre préliminaire où nous insistons sur les connections entre ces différents points de vue.