Sujet : Etude des graphes t-couvrants et application à la visualisation

Responsable : Olivier Baudon et André Raspaud
Téléphone : 05.40.00.69.21
e-mail : baudon@labri.fr
Site Web : dept-info.labri.fr/~baudon
Equipe : Combinatoire et Algorithmique

Présentation du sujet :

Soit H = (V, E(H)) un graphe partiel de G = (V, E(G)).
Le facteur d'étirement dans H d'une paire de sommets x,y est le rapport entre la distance dans H entre x et y sur la distance dans G entre
ces mêmes sommets : fe(x,y) = d_H(x,y) / d_G(x,y).
H est dit t-couvrant si et seulement le facteur d'étirement de toute paire de
sommets est au plus t. t est alors appelé le facteur d'étirement de H. La plus petite valeur possible de t pour que H soit t-couvrant est appelé
l'indice d'étirement de H.
Ce paramètre a été introduit par Peleg et Ullman en 1987 et étudié en particulier dans le cadre des réseaux d'interconnexion.

Nous nous intéressons à ce paramètre dans le but cette fois de l'appliquer à la visualisation de grands graphes.
Parmi les objectifs recherchés, citons :
1) compléter un arbre couvrant donné en y insérant les arêtes en fonction de la valeur de leur facteur d'étirement. En particulier, le dessin de l'arbre peut être modifié de façon à faciliter cette insertion. Il convient dans ce cas de distinguer entre un dessin vertical de l'arbre et un dessin circulaire.
2) concevoir une heuristique permettant d'obtenir un arbre couvrant ayant un facteur d'étirement proche du minimum possible (la recherche du minimum est un problème NP-difficile). En particulier, on pourra s'intéresser à la sous-classe des arbres couvrants composés de plus courtes chaînes de G.
3) rechercher un graphe partiel planaire de G ayant un petit facteur d'étirement. En particulier, parmi les graphes planaires ayant un arbre couvrant T donné.
4) Effectuer une mise à jour du facteur d'étirement des arêtes d'un co-arbre lorsque l'on passe d'un abre de plus courtes chaînes de racine x à un arbre de plus courtes chaînes ayant comme racine un voisin de x.


Mot-clés : Graphes, Facteur d'étirement, Graphes t-couvrant

Références :
D. Peleg and A.A. Schäffer, "Graph spanners" J. Graph Theory 13:99-116, 1989.
L. Cai and D. Corneil, "Tree spanners", SIAM J. Discrete Math., 8:359-387, 1995.