Théorème de Schnyder

En théorie des graphes, le théorème de Schnyder est une caractérisation des graphes planaires par la dimension d'ordre de leurs ensembles d'incidence partiellement ordonnés. Il porte le nom de Walter Albert Schnyder, qui en a publié la démonstration en 1989^[1].

L'ensemble d'incidence ${\displaystyle P(G)}$ d'un graphe non orienté ${\displaystyle G=(V,E}$) avec ensemble de sommets ${\displaystyle V}$ et ensemble d'arêtes ${\displaystyle E}$ est l'ensemble partiellement ordonné de hauteur 2 dont les éléments sont les éléments de ${\displaystyle V\cup E}$. L'ordre partiel est défini par ${\displaystyle x<y}$ si ${\displaystyle x}$ est un sommet, ${\displaystyle y}$ est une arête et ${\displaystyle x}$ est l'une des deux extrémités de ${\displaystyle y}$.

La dimension d'ordre d'un ordre partiel est le plus petit nombre d'ordres totaux dont l'intersection est cet ordre partiel ; un tel ensemble d'ordres est appelé un réalisateur de l'ordre partiel.

Le théorème de Schnyder dit qu'un graphe ${\displaystyle G}$ est planaire si et seulement si la dimension d'ordre de ${\displaystyle P(G)}$ est au plus égale à trois.

Le théorème a été généralisé par Brightwell et Trotteur^[2],[3], qui ont donné une borne précise pour la dimension des ensembles partiellement ordonnés de hauteur 3 formés de manière analogue à partir des sommets, arêtes et faces d'un polyèdre convexe, ou plus généralement d'un graphe planaire dessiné : dans les deux cas, la dimension d'ordre de l'ensemble partiellement ordonné est au plus égale à quatre. Cependant, ce résultat ne peut être généralisé aux polytopes convexes de dimension supérieure, car il existe des polytopes de dimension quatre dont le treillis des faces ont une dimension d'ordre non bornée.

Plus généralement, et dans des simpliciaux abstraits complexes, la dimension d'ordre du poset des faces est au plus 1 + d, où d est la dimension minimale d'un espace euclidien qui permet une réalisation géométrique du complexe^[4],[5].

Comme observé par Schnyder, l'ensemble ordonné d'incidence d'un graphe ${\displaystyle G}$ est de dimension d'ordre 2 si et seulement si le graphe est un chemin ou un sous-graphe d'un chemin. En effet, lorsqu'un ensemble d'incidence est de dimension d'ordre deux, son seul réalisateur possible est constitué de deux ordres totaux qui, restreints aux sommets du graphe, sont inverses l'un de l'autre. Deux autres ordres auraient une intersection contenant une relation d'ordre entre deux sommets, ce qui est interdit pour les posets d'incidence. Pour ces deux ordres sur les sommets, une arête entre deux sommets consécutifs peut être ajoutée dans l'ordre en la plaçant immédiatement après l'extrémité la plus récente de l'arête, mais aucune autre arête ne peut l'être.

Dans un graphe qui peut être coloré avec quatre couleurs, son ensemble d'incidence a une dimension d'ordre au plus quatre^[1].

L'ensemble partiellement ordonné d'incidence d'un graphe complet à n sommets a une dimension d'ordre ${\displaystyle \Theta (\log \log n)}$^[6].

• G. Brightwell et W. T. Trotter, « The order dimension of convex polytopes », SIAM Journal on Discrete Mathematics, vol. 6, n^o 2,‎ 1993, p. 230–245 (DOI 10.1137/0406018, MR 1215230).
• G. Brightwell et W. T. Trotter, « The order dimension of planar maps », SIAM Journal on Discrete Mathematics, vol. 10, n^o 4,‎ 1997, p. 515–528 (DOI 10.1137/S0895480192238561, MR 1477654, CiteSeer^x 10.1.1.127.1016).
• P. Ossona de Mendez, « Geometric realization of simplicial complexes », Lecture Notes in Computer Science, Springer-Verlag, vol. 1731 « Jan Kratochvíl (éd) : Proc. Int. Symp. Graph Drawing (GD 1999) »,‎ 1999, p. 323–332 (ISBN 978-3-540-66904-3, DOI 10.1007/3-540-46648-7_33 , MR 1856785).
• P. Ossona de Mendez, « Realization of posets », Journal of Graph Algorithms and Applications, vol. 6, n^o 1,‎ 2002, p. 149–153 (DOI 10.7155/jgaa.00048 , MR 1898206, lire en ligne).
• W. Schnyder, « Planar graphs and poset dimension », Order (journal), vol. 5, n^o 4,‎ 1989, p. 323–343 (DOI 10.1007/BF00353652, MR 1010382, S2CID 122785359).
• J. Spencer, « Minimal scrambling sets of simple orders », Acta Mathematica Academiae Scientiarum Hungaricae, vol. 22, n^os 3–4,‎ 1971, p. 349–353 (DOI 10.1007/bf01896428, MR 0292722, S2CID 123142998).

• Portail des mathématiques