JCJC SIMI 2 - JCJC - SIMI 2 - Science informatique et applications

Graphes Plongés et leurs Structures Orientées – EGOS

Structure orientée des cartes de genre supérieur et leurs applications

-

Généralisation des résultats structurels concernant les graphes planaires au cas du tore et au délà

Lorsque les premiers problèmes de théorie des graphes sont apparus, ils étaient liés aux graphes plongés. En effet, les graphes considérés dans le problème des ponts de Koenigsberg ou encore ceux considérés dans le problème des 4 couleurs sont planaires (i.e. plongés dans le plan sans croisement des courbes représentant les arêtes). Une généralisation naturelle des graphes planaires sont les graphes plongés dans les surfaces telles que la sphère ou le tore et sont appelés cartes. <br />Le tore est l'un des objets centraux de ce projet. Il possède une certaine propriété « d'homogénéité » et peut être vu comme un modèle de surface planaire périodique. Par exemple, en physique statistique, les modèles toriques sont souvent préférés aux modèles planaires pour éviter de devoir considérer des conditions particulières au bord. De nombreuses propriétés et constructions combinatoires concernant le cas planaire demandent donc à être étendues au cas torique et plus généralement aux cas des surfaces de genre supérieur.

Dans le plan, beaucoup de familles de
graphes possèdent des structures orientées, qui sont des orientations et colorations des arêtes satisfaisant des contraintes locales particulières. Par exemple, les graphes planaires bipartis 2-connexes admettent des 2-orientations, les graphes planaires 3-connexes admettent des forêts de Schnyder, les triangulations planaires 4-connexes admettent des structures transverses. Ces structures sont en bijection avec de nombreux objets combinatoires tels que les systèmes de contact de polygones, les triangulations TD-Delaunay ou encore les mots de Dyck. Elles ont également de nombreuses applications en informatique fondamentale telles que l'encodage compact, le dessin de graphes avec arêtes rectilignes, les sous-graphes d'étirement bornés, etc.

Ce projet a pour but de généraliser ces structures orientées à des surfaces de genre supérieur. Naturellement le premier cas a étudier est celui du tore (genre 1). L'homogénéité du tore se traduit par la possibilité de doter les cartes toriques de certaines orientations satisfaisant la même propriété locale partout. Par exemple, les triangulations toriques peuvent être dotées d'orientations où chaque sommet à exactement trois arêtes sortantes. De telles orientations généralisent les forêts de Schnyder et forment le cœur de notre étude.

Généralisant des résultats de Felsner et Ossona de Mendez dans le plan, nous avons exhiber une partition naturelle de l'ensemble des orientations d'une carte en treillis distributifs. Dans le cas du tore, cela nous a permis de distinguer une certaine orientation « canonique » qui permet d'obtenir de nouvelles bijections. Cela a d'importantes conséquences pour compter, générer aléatoirement ou encore encoder optimalement les triangulations toriques.

Nous espérons obtenir d'autres applications des objets étudiés.

Ce projet traite de recherche fondamentale, nous avons donc publier nos résultats dans des revues internationales de haut niveau : “Journal of Combinatorial Theory, Ser. A”, “Discrete and Computational Geometry”, “Combinatorics, Probability and Computing”, etc. ainsi que dans des conférences  : Graph Drawing, Eurocomb, SoCG, EuroCG, Latin, IPEC, MFCS, ESA, etc. De plus nous avons organisé quatre workshops à Montpellier (2012), Paris (2013), Bordeaux (2014), Grenoble (2016).

Lorsque les premiers problèmes de théorie des graphes sont apparus, ils étaient liés aux graphes plongés. En effet, les graphes considérés dans le problème des ponts de Koenigsberg ou encore ceux considérés dans le problème des 4 couleurs sont planaires (i.e. plongés dans le plan sans croisement des courbes représentant les arêtes). Une généralisation naturelle des graphes planaires sont les graphes plongés dans les surfaces telles que la sphère ou le tore. Le but de ce projet est d'étudier de tels graphes.
Dans le plan, beaucoup de familles de graphes possèdent des structures orientées, qui sont des orientations et colorations des arêtes satisfaisant des contraintes locales particulières. Par exemple, les graphes planaires bipartis 2-connexes admettent des 2-orientations, les graphes planaires 3-connexes admettent des forêts de Schnyder, les triangulations planaires 4-connexes admettent des structures transverses. Ces structures sont en bijection avec de nombreux objets combinatoires tels que les systèmes de contact de polygones, les triangulations TD-Delaunay ou encore les mots de Dyck. Elles ont également de nombreuses applications en informatique fondamentale telles que l'encodage compact, le dessin de graphes avec arêtes rectilignes, les sous-graphes d'étirement bornés, etc.
Ce projet a pour but de généraliser ces structures orientées à des surfaces de genre supérieur et à des objets de dimension supérieure. De récents résultats ont été obtenus dans cette direction par certains membres du projet, ouvrant de nouveaux axes de recherche. Les premières étapes consisteront à trouver une généralisation naturelle des structures considérées, prouver leur existence et étudier leurs propriétés. Ensuite, le but sera de trouver des bijections et des applications de ces objets qui étendent le cas planaire.

Coordinateur du projet

Monsieur Benjamin LEVEQUE (Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier) – benjamin.leveque@lirmm.fr

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

CNRS-LIRMM Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Aide de l'ANR 157 872 euros
Début et durée du projet scientifique : septembre 2012 - 36 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter