Stage de recherche UM2 proposé par E. Gioan

Proposition de stage de recherche, Université Montpellier 2, année 2009-2010

Dessins de graphes avec canevas planaire et mutations de triangles

Encadrant : Emeric Gioan (LIRMM, équipe AlGCo : Algorithmes, Graphes et Combinatoire)
Thème principal : codage des dessins de graphes
Autres mots-clés : théorie des graphes, structures logiques de données, géométrie algorithmique
Prérequis : un peu de théorie des graphes et une bonne rigueur formelle
Résumé : Sur le plan théorique, il s'agit d'étudier les dessins de graphes dans le plan pour lesquels on connait déjà le dessin d'un sous-graphe planaire. En bref, on se demande quelles informations sur les croisements et positions entre les arêtes du sous-graphe et celles qui ne sont pas dans le sous-graphe permettent de reconstruire le dessin tout entier, éventuellement à des transformations simples près (par exemple des mutations de triangles consistant à passer une portion d'arête de l'autre coté du croisement de deux autres arêtes sans toucher le reste du dessin). Sur le plan algorithmique, il s'agit de reconstruire efficacement un dessin de graphe (ou bien un représentant de sa classe d'équivalence lorsque des mutations sont autorisées) à partir de son codage combinatoire. La programmation de ces algorithmes pour une présentation sur ordinateur, voire pour le développement d'une interface graphique, sera également la bienvenue.

Présentation détaillée du sujet.

Les dessins de graphes sont une branche active de la théorie des graphes (colloques réguliers, nombreuses publications...).

L'approche proposée dans ce sujet est le codage des dessins de graphes par des structures combinatoires (ou logiques), pour permettre un traitement des dessins de graphe de façon directement structurelle sans s'occuper des positions réelles des points du dessin. Sur le plan théorique, le problème considéré consiste à étudier un allègement de la structure afin de n'en retenir si possible que l'information géométrique à laquelle on s'intéresse (par exemple connaître le croisement des routes dans une carte géographiques mais pas la façon exacte dont les routes se croisent). Sur le plan pratique, le but est d'utiliser ces structures afin de faciliter la représentation et le traitement des données utiles.

Formellement, on considère une surface S, qui est a priori simplement le plan (par exemple le plan de l'écran d'ordinateur pour une visualisation de graphe), ou bien la sphère de dimension 3 (ce qui est très similaire en ajoutant un point à l'infini au plan).

Rappel : un homéomorphisme de S est une application bijective de S qui transforme une courbe continue en courbe continue, et ne change pas les relations d'intersection des courbes continues entre elles. Intuitivement, un homéomorphisme permet de déformer un dessin en respectant la forme de l'objet, dans le sens où il respecte les positions relatives des parties de l'objet (un point à l'intérieur d'une région reste à l'intérieur de cette région, deux traits qui se coupent continuent de se couper le même nombre de fois et de la même façon, etc...).

On appelle dessin de graphe sur la surface S une application qui associe un point à chaque sommet du graphe G=(V,E), et une courbe a chaque arête (homéomorphe à un segment), de sorte que :

deux sommets ne sont pas représentés par un même point
la courbe représentant une arête joint les points représentant ses extrémités
deux courbes représentant des arêtes se coupent au plus une fois, et elles se croisent si elles se coupent
trois courbes représentant des arêtes ne se coupent pas en un même point (sauf si c'est une extrémité communne des trois arêtes)

Pour coder un dessin de graphe (à homéomorphisme près), on peut utiliser des structures de données de différents niveaux de précision :

La carte est la donnée, pour chaque sommet, de l'ordre circulaire des arêtes ayant ce sommet pour extrémité, autour du point représentant ce sommet. Formellement, la carte est donnée par un sous-ensemble de V*E*E*E de sorte que (x,e,f,g) est dans l'ensemble si f est entre e et g autour de x. On sait (voir par exemple [3]) que la carte d'un dessin de graphe planaire sans croisement d'arêtes dans le plan détermine le dessin dès que l'on connait un point (appelé coin) touchant la région non bornée du plan délimitée par le dessin du graphe.
Le sous-croquis est la donnée, en plus de la carte, de l'ensemble des paires d'arêtes qui se coupent. Formellement, le croquis est donné, en plus de la carte, par un sous-ensemble de E*E de sorte que (e,f) est dans l'ensemble si e et f se croisent dans le dessin.
Le croquis est la donnée, en plus du sous-croquis, pour chaque arête, de l'ordre des arêtes qui coupent cette arête. Formellement, le croquis est donné, en plus du sous-croquis, par un sous-ensemble de E*E*E*E de sorte que (e,f,g,h) est dans l'ensemble si f,g,h coupent e et g est entre f et h le long de e. On sait d'après [1] que le croquis d'un dessin de graphe dans le plan détermine le dessin dès que l'on connait un coin. Ainsi, à homéomorphisme près et à coin fixé, on peut identifier les dessins de graphes dans le plan et les croquis.

Dans le cas d'un dessin de graphe complet, d'après [2], on a les résultats suivants :

l'ensemble des croisements, ou bien également la carte, détermine le sous-croquis par des formules logiques du premier ordre.
le sous-croquis détermine le dessin de graphe (i.e. le croquis) à une suite de mutations de triangles près (ce qui généralise le théorème de Ringel sur les arrangements uniformes de pseudodroites).

Une mutation de triangle consiste à passer une portion d'arête de l'autre coté du croisement de deux autres arêtes sans toucher le reste du dessin. C'est la transformation représentée sur la figure ci-dessous. Bien sûr, une mutation de triangle ne change pas le sous-croquis du dessin (mais change le croquis puisqu'elle change l'ordre des intersections le long des arêtes).

Sur le plan théorique, le sujet de ce stage est d'étudier la généralisation du résultat 2 précédent (et éventuellement de résultats du type 1) aux dessins de graphe avec un canevas planaire :

un canevas planaire d'un dessin du graphe G, introduit dans [1], est un dessin sans croisement d'arêtes d'un sous-graphe planaire de G, 2-connexe et passant par tous les sommets de G. Ainsi les arêtes qui ne sont pas dans le sous-graphe vont couper des arêtes du sous-graphe, et on se demande quelles informations sur les croisements et positions relatives entre ces arêtes et celles du sous-graphes déterminent tout ou partie du dessin du graphe de départ.

Questions principales du stage :

Théorique : est-ce que le sous-croquis et un canevas planaire d'un dessin de graphe déterminent le dessin de graphe à une suite de mutations de triangles près ? si oui, quel algorithme employer ?
Il semble que la généralisation des techniques de [2] devrait être a priori assez directe, mais ça reste à regarder précisément, et à rédiger proprement... Il faudra donc pour cela lire attentivement la majeure partie de l'article [2], et en reprendre les résultats un par un de façon un peu plus générale, en faisant preuve d'une grande rigueur formelle et d'un minimum d'intuition géométrique.
Algorithmique : connaissant le croquis (resp. le sous croquis) d'un dessin de graphe avec canevas planaire, comment reconstruire et dessiner efficacement le dessin (resp. un représentant ayant ce sous-croquis) ? quelles sont les complexités à prendre en compte ?
Présentation : la mise en place des résultats théoriques et algorithmiques précédents pourra se faire via une interface graphique à programmer, consistant en faire apparaître à l'écran les dessins à partir de leurs codages, et éventuellement leurs transformations (mutations de triangles).

Questions annexes (selon les motivations du stagiaire) :

Logique : peut-on déduire la carte de l'ensemble des croisements, et réciproquement, dans un dessin de graphe avec canevas planaire ? et si oui en quelle logique ?
Structures de données : y'a t'il d'autres structures de données intermédiaires ou significatives, par exemple la position des sommets par rapport aux cycles sans croisement ?
Transformations du dessin : y'a t'il d'autres transformations du dessin que les mutations de triangles liées à des structures de données significatives ?
Topologie : peut-on généraliser ce type de résultats à d'autres surfaces que le plan ou la sphère ?
Classes de graphes : peut-on généraliser ce type de résultats à d'autres classes de graphes ?
Applications : peut-on envisager des applications de ces sujets, par exemple pour les bases de données géographiques, ou bien pour la visualisation de graphes ?
Autres : le stagiaire sera libre de proposer et d'étudier d'autres approfondissements du sujet...

Références :

[1] Courcelle, B.: The monadic second-order logic of graphs XIII: graph drawings with edge crossings. Th. Comp. Sci. 244(2000) 63--94

[2] Gioan, E.: Complete graph drawings up to triangle mutations. Proceedings WG05, LNCS 3787 (2005) 139--150

[3] Mohar, B., Thomassen, C.: Graphs on surfaces. John Hopkins University Press, Baltimore, MD (2000).