Graphes, Algorithmes et TOpologie – GATO

Le concept de graphe est omniprésent dans les sciences modernes : cette notion basique en combinatoire et algorithmique est utilisée comme un outil d'abstraction dans une variété sans cesse croissante de contextes allant des réseaux sociaux à la modélisation des processus biologiques. Si la théorie des graphes est riche et intéressante en toute généralité, il apparaît dans de nombreux contextes applicatifs que les graphes considérés sont munis d'une structure supplémentaire qui doit être prise en compte, à la fois pour faire ressortir l'objet de la modélisation et pour bénéficier de solutions algorithmiques potentiellement plus efficaces. Les exemples vont des célèbres lois de puissance et les propriétés des graphes petits mondes au phénomène de réduction de dimension des données géométriques.

Notre projet se concentre sur la structure combinatoire et topologique propre aux graphes plongés sur une surface de faible genre. Les objets résultants, appelés "cartes", sont fondamentaux en infographie et en modélisation géométrique où les cartes sont à la base des structures de données classiques pour la manipulation des maillages surfaciques. Les cartes jouent également un rôle important dans la célèbre théorie des mineurs de Robertson et Seymour et dans ses conséquences algorithmiques : un résultat remarquable de cette théorie est que, pour de nombreux problèmes, toute amélioration de leur complexité dans le cas des graphes de genre borné s'étend directement à la (bien plus large) classe de graphes avec des mineurs interdits. Les propriétés combinatoires des cartes se sont également avérées très pertinentes pour l'étude des modèles aléatoires de surfaces comme ceux considérés dans la communauté probabiliste et en physique, en relation avec certains modèles mathématiques de la gravité quantique.

Les membres de notre projet ont été impliqués ces dernières années dans divers progrès algorithmiques et combinatoires en lien direct avec les cartes: on peut citer l'optimisation de courbes sur des surfaces, des structures de données succinctes pour les maillages, la programmation dynamique sur les graphes de genre borné, ou des décompositions bijectives de différentes familles de cartes planaires. Nous sommes convaincus que notre groupe a la bonne taille et l'expertise nécessaire pour s'attaquer aux défis posés par la manipulation des cartes de genre non-nul. Voici quelques-unes des problématiques que nous comptons résoudre.

La structure combinatoire des cartes planaires est maintenant bien comprise grâce à la notion de forêt de Schnyder. L'un de nos principaux objectifs est d'étendre ces forêts aux cartes non planaires. Un autre paramètre fondamental pour les cartes de genre supérieur est la longueur minimale d'un cycle non-contractile. Ce paramètre, appelé largeur en arêtes, mesure la planarité locale d'une carte. Puisqu'une carte a en moyenne une grande largeur en arêtes, il est pertinent d'étudier la dépendance des propriétés structurelles des cartes par rapport à ce paramètre. Nous nous concentrerons également sur des familles spécifiques de cartes, telles que les triangulations irréductibles, pour lesquelles des décompositions topologiques comme les décompositions en pantalons apparaissent plus appropriées pour l'étude de leurs structures. Comprendre la structure des cartes est crucial lors de l'énumération, l'échantillonnage aléatoire ou même pour la représentation des cartes. La représentation des cartes non planaires, c.-à-d. leur plongement géométrique, à des fins de visualisation, de plaquage de texture, ou d'analyse de réseaux est un autre de nos défis.
Parallèlement à ces recherches théoriques, nous souhaitons implémenter l'état de l'art concernant les algorithmes pour les cartes sur les surfaces et fixer les connaissances dans ce domaine dans un handbook dédié.