Sujet : Représentation implicite pour les graphes de genre borné

Responsable : Cyril Gavoille
Téléphone : 05.40.00.88.12 / 84.28
e-mail : gavoille@labri.fr
Site Web : http://dept-info.labri.fr/~gavoille
Equipe : Combinatoire et Algorithmique: Graphes & Applications

Présentation du sujet :

Un graphe universel pour une famille de graphes F est un graphe Un
tel que tout graphe de F à n sommets est un sous-graphe induit de Un.

L'objectif est de construire des graphes universels avec le plus petit nombre de sommets possibles. Par exemple, il est possible de construire un graphe universel de O((nlogn)3) sommets pour la famille des graphes planaires [2].

Dans cette étude on s'intéresse au cas où F est la famille des graphes de genre borné, c'est-à-dire l'ensemble des graphes que l'on peut dessiner sur une surface de genre borné (par exemple les sphères sont des surface de genre 0 et les tore de genre 1) sans que deux arêtes ne se coupent (cette famille inclut les graphes planaires). En particulier on cherche à savoir s'il existe pour cette famille, un graphe universel de O(n3+ε ) sommets avec 0<ε<1.

Une approche classique pour ce problème est de construire une représentation implicite de chaque graphe de la famille, c'est-à-dire un schéma d'adjacence compact. Plus précisément, il s'agit de construire deux fonctions L et A vérifiant : pour tout graphe torique G et pour toute paire {x,y} de sommets de G,

  1. L(x) est une étiquette associée au sommet x (étiquette écrite en binaire) ;
  2. la longueur de L(x) est au plus k bits (pour une certaine fonction k=k(n));
  3. A(L(x),L(y))=1 si et seulement si x est adjacent y.
Il n'est pas difficile de voir (cf. [4]) que si L et A existent pour la famille F alors il existe un graphe universel de O(2k ) sommets pour F.

Dans cette thèse il s'agira donc de construire de tels schémas pour les graphes de genres bornés. Une approche possible consistera à généraliser les arbres de Schnyder [5] des graphes planaires aux graphes de genre g. Plus concrètement il s'agira de construire, pour toute triangulation à n sommets d'une surface de genre g (ayant donc 3n+O(g) arêtes par la formule d'Euler), une partition de ses arêtes en trois arbres de n-O(1) sommets plus O(g) d'arêtes.

Mot-clés : théorie des graphes, algorithme, graphe planaire

Références :
[1] S. Alstrup, T. Rauhe.
Small Induced-Universal Graphs and Compact Implicit Graph Representations.
43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS),
IEEE Computer Society Press, pp. 53-62, nov 2002.

[2] F.R.K. Chung.
Universal graphs and induced universal graphs.
Journal of Graph Theory, 14:443-454, 1990.

[3] C. Gavoille.
A Note on Implicit Representation of Graphs.
LaBRI, University of Bordeaux, 351, cours de la Libération,
33405 Talence Cedex, France, Research Report, RR-1268-01, dec 2001.
http://www.labri.fr/Labri/Publications/Rapports-internes/RR-126801.ps.gz

[4] S. Kannan, M. Naor, et S. Rudich.
Implicit Representation of Graphs.
SIAM Journal on Discrete Mathematics, 5:596-603, 1992

[5] W. Schnyder.
Embedding planar graphs on the grid.
1st Symposium on Discrete Algorithms (SODA), ACM-SIAM, pp. 138-148, 1990.