Dans cet exposé nous allons parler de deux résultats profonds, fournissant des caractérisations fines de la notion de planarité d’un graphe: elles sont célèbres et connues sous le nom de forêts de Schnyder et invariant de Colin de Verdière, respectivement.
Les forêts de Schnyder constituent une jolie structure combinatoire, dont l’appellation est due à W. Schnyder, qui l’introduisit sous le nom de réaliseurs, pour les liens étroits avec certaines propriétés des ordres partiels. L’une des premières applications conduit justement à un nouveau critère de planarité, qui peut s’exprimer en termes de dimension d’ordres partiels: un graphe est planaire si et seulement si l’ordre partiel d’incidence arêtes/sommets est au plus 3.
De nature complètement différente est l’invariant que Yves Colin de Verdière introduisit en 1990, pour caractériser la planarité d’un graphe en termes de propriétés spectrales. En gros, pour un un graphe G, l’invariant µ (G) peut se voir comme la multiplicité de la deuxième valeur propre d’une certaine matrice Laplacienne associée au graphe G. Il est alors possible d’établir le résultat fondamental suivant: un graphe est planaire, si et seulement si µ (G)≤ 3.
Nous ne manquerons pas d’esquisser les propriétés géométriques que font des forêts de Schnyder et des matrices de Colin de Verdière deux outils fondamentaux dans le domaine du dessin des graphes. Ce qui motive, à notre avis, l’exploration des liens possibles entre ces deux jolies caractérisations.
This document was translated from LATEX by HEVEA.