Introduction
L'objet de ce projet est l'étude de la caractérisation des graphes planaires fournies par Y. Colin de Verdière, et ses relations avec la représentation de polyèdres. Comme montré par Colin de Verdière [3], on peut définir un invariant qui permet d'exprimer un nouveau critère de planarité: en gros, on peut dire qu'un graphe G est planaire si et seulement si la multiplicité de la deuxième valeur propre d'une certaine matrice laplacienne généralisée L associée à G est au plus 3.
Il existe aussi une preuve élégante (et courte) et purement combinatoire du résultat de Colin de Verdière, due à Hein Van Der Holst [6]: une présentation très pédagogique de la preuve, dans le cas où le graphe est 3-connexe, est fournie dans [7].
Comme montré par Lovasz et Scrijver (voir [1] et [4]), les notions mentionnées ci-dessus conduisent aussi à des méthodes pour dessiner un graphe planaire sur la sphère (sans croisements): cela fait intervenir les propriétés spectrales de la matrice L. Plus précisément, si on dénote par [v0, v1, v2, v3, ...] les n vecteurs propre de la matrice L, alors les composantes des trois vecteurs propres v1, v2, v3 peuvent etre utilisées determiner les coordonnées des points d'une représentation du graphe G en 3D: dans ce cas on obtient un polyèdre convexe en 3D, contenant l'origine.
Représentations de graphes planaires (rappel de choses vues en cours)
On se souvient maintenant de deux résultats fondamentaux de la théorie des graphes: le théorème barycentrique de Tutte et le théorème de Steinitz, qui peuvent s'énoncer en gros comme suit:
| Théorème
(Steinitz) Tout graphe planaire 3-connexe est isomorphe au 1-squelette d'un polyèdre convexe en 3D.  Fig 1: corresondence entre graphes planaire 3-connexes et polyèdre convexes. |
Théorème barycentrique (Tutte) Tout graphe planaire 3-connexe G
admet une représentation convexe, où les points (leurs
coordonnées)
correspondant aux sommets internes peuvent s'éxprimer comme
combinaison
convexe de leurs voisins dans G.
Le théorème de Tutte est un outil fondamental dans le domaine du dessin des graphes: il dit, en gros, qu'une fois choisi le plongement pour la face externe (un polygone convexe en 2D), pour tous les dessins planaires de G, on peut décrire la positions d'un point comme une certaine combinaison barycentrique de ses voisins. |
  |
| Fig 2: Exemples de dessins
planaires obtenus à l'aide de la méthode barycentrique de
Tutte. |
Dessins de graphes planaires sur la sphère
Dans un travail récent Gotsman, Gu et Sheffer [5] ont montré comment généraliser le théorème barycentrique de Tutte (valable dans le plan uniquement) au cas de triangulations sphériques (triangulations dont les sommets appartiennent à la sphère unité, et où les aretes sont représentées par des arcs de courbes).
Théorème barycentrique (sur la sphère [5]) Etant donné graphe planaire
3-connexe G plongé en 3D, les positions des sommets
définissent une triangulation sphérique si et seulement
sipour tout sommet v, on peut exprimer la position de v comme
combinaison convexe des positions de ses voisins (les points
étants projetés sur la sphère).
Ce résultat fait intervenir les propriétés étudiées dans [1,4], qui établissent un lien entre matrices laplaciennes généralisées et les représentations en 3D de polyèdres: cela fait intervenir des jolies propriétés de géométrie convexe concernant les polytopes polaires duaux. |
 |
Malheureusement la construction due à Lovasz [1], ne fourni pas une manière "effective" de trouver une matrice de Colin de Verdière d'un polyèdre donné. Dans un travail plus récent Schaefer, Warren et Desbrun [2] ont donné une nouvelle interprétation de la construction de Lovasz: cette fois la construction est explicite, et fourni une interprétation géométrique plus intuitive des relations entre polyèdres convexes et les correspondants polytopes polaires duaux. |
 Fig 4: Polyèdres convexes (dessinées en gris) et polytopes polaires duaux (en bleue) en 2D et 3D (images produites par Ju, Schaefer, Warren and Desbrun [2]). |
Objectifs
du projet:
L'objectif principal de ce projet est une "partielle compréhension" des propriétés spectrales des graphes et de leur role dans le domaine du dessin des graphes. En particulier, il serait intéressant de s'intéresser aux relations existantes entre polyèdres convexes et matrices de Colin de Verdière (comme expliqué dans [1, 2, 4, 5, 7]).
Etant donnée la quantité des notions utilisées dans ce contexte (combinatoire, théorie spectrale des graphes, géométriqe convexe, dessin de graphes, ...), on ne demande pas une connaissance et compréhension exhaustive des travaux mentionnés ci-dessus.
Vous avez la liberté de choisir une ou plusieurs applications (avec implementation java) faisant intervenir quelques unes des propriétés mentionnées.
Voici quelques suggestions:
- Une possible application est la réalisation d'un programme qui met en place la méthode décrite dans [2] (section 4.2) pour le calcul d'une matrice de Colin de Verdière correspondante à un polyèdre donné.
- une autre application serait l'implementation de la méthode décrite dans [5], pour plonger un graphe planaire sur la sphère: attention, cette méthode fait nécessite un peu de reflexion (puisque elle fait intervenir des systèmes d'équations de degré 2... apparement il n'existe pas de librairies disponibles en Java pour résoudre ces systèmes)
- ...
Mot clés: dessin de graphes, théorème de Steinitz, théorie spectrale des graphes, invariant de Colin de Verdière, représentations de polyèdres.
Références:
[1] Laszlo Lovasz, Steinitz representations of polyhedra and the Colin de Verdière number, J. Comb. Theory, Ser. B , 2000. (online version)
[2] Tao Ju, Scott Schaefer, Joe D. Warren and Mathieu Desbrun, A geometric construction of coordinates for convex polyhedra using polar duals, Proc. of Symposium on Geometry Processing, 181-186, 2005. (online version)
[3] Y. Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, Journal of Combinatorial Theory, Series B 50 (1990) 11-21.
[4] L. Lovasz and A. Schrijver, On the null space of a Colin de Verdière matrix, Annales de l’Institute Fourier 49 (1999), 1017–1026. (online version)
[5] Craig Gotsman and Xianfeng Gu and Alla Sheffer, Fundamentals of spherical parameterization for 3D meshes, ACM Trans. Graph.(2003), vol 22(3), 358-363. (online version)
[6] H. van der Holst, A short proof of the planar characterization of Colin de Verdière, Journal of Combinatorial Theory, Series B, vol. 65, pp. 269-272, 1995.
Suggestion: pour une présentation pédagogique et self-contained des propriétés de la matrice laplacienne (et des laplaciennes généralisées), nous suggérons la lecture du chapitre suivant:
[7] Godsil and Royle, The Laplacian of a Graph , chap. 13 in "Algebraic Graph Theory", Graduate Texts in Mathematics, 207, Springer-Verlag., pp. 279-306, 2001.
Remarque: vous pouvez nous écrire par e-mail, dans le cas où vous désiriez obtenir la version éléctronique de certaines de références listées ci-dessus.