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.