Théorème de Fáry

Dans le domaine mathématique de la théorie des graphes, le théorème de Fáry stipule que tout graphe planaire simple peut être tracé dans un plan avec des arêtes rectilignes. Autrement dit, la possibilité de dessiner les arêtes d'un graphe par des courbes plutôt que par des segments de droites ne permet pas de dessiner une classe plus large de graphes. Le théorème porte le nom d'István Fáry, bien qu'il ait été prouvé indépendamment par Klaus Wagner en 1936, Fáry en 1948, et Sherman K. Stein en 1951.

Démonstration

Illustration de l'étape d'induction dans la démonstration du théorème de Fáry.

On peut prouver le théorème de Fáry en effectuant un raisonnement par récurrence. Soit G un graphe planaire simple à n sommets ; on peut ajouter des arêtes si nécessaire de sorte que G soit un graphe planaire maximal. Si n < 3, le résultat est trivial. Si n ≥ 3, toutes les faces de G sont des triangles, car nous pourrions ajouter une arête à un face non triangulaire tout en préservant la planarité, ce qui contredirait l'hypothèse de planarité maximale. Choisissons trois sommets a, b, c formant une face triangulaire de G. Nous allons montrer par récurrence sur n qu'il existe un plongement en ligne droite de G dont la face extérieure est le triangle abc. De plus, ce plongement est tel que les sommets, les arêtes et les faces du nouveau dessin correspondent à ceux de l'ancien dessin, de telle sorte que toutes les incidences entre les arêtes, les sommets et les faces, et pas seulement entre les sommets et les arêtes, soient préservées. En initialisation, le résultat est trivial lorsque n = 3 et a, b et c sont les seuls sommets de G. Ainsi, nous pouvons supposer n ≥ 4.

D'après la formule d'Euler pour les graphes planaires, G possède 3n − 6 arêtes ; de manière équivalente, si l'on définit la déficience d'un sommet s de G comme étant égale à $6-\deg(s)$, la somme des déficiences est égale à 12 . Étant donné que G possède au moins quatre sommets et que toutes les faces de G sont des triangles, les sommets de G ont un degré au moins égal à trois et donc une déficience d'au plus trois. Il y a donc au moins quatre sommets avec une déficience strictement positive. En particulier, on peut choisir un sommet s avec au plus cinq voisins qui soit différent de a, b et c . Soit G' formé en supprimant s dans G et en retriangulant la face f formée en supprimant s. Par hypothèse de récurrence, G' possède un plongement en ligne droite dont abc est la face extérieure. En supprimant les arêtes qui ont été ajoutées pour créer G', on obtient la face f, qui est maintenant un polygone P ayant au plus cinq côtés. Pour compléter le dessin d'un plongement en ligne droite de G, s doit être placé dans le polygone et joint par des lignes droites aux sommets du polygone. D'après le théorème de la galerie d'art, il existe un point intérieur à P où s peut être placé de telle sorte que les arêtes allant de s aux sommets de P ne croisent aucune autre arête, complétant ainsi la démonstration.

Résultats associés

De Fraysseix, Pach et Pollack ont montré comment trouver en temps linéaire un tracé en ligne droite dans une grille de dimensions linéaires dans la taille du graphe, donnant un ensemble de points universel de taille quadratique. Une méthode similaire a été suivie par Schnyder pour prouver des limites améliorées et une caractérisation de la planarité basée sur l'ordre partiel d'incidence. Ses travaux ont mis l'accent sur l'existence d'une partition particulière des arêtes d'un graphe planaire maximal en trois arbres connus sous le nom de bois de Schnyder.

Le théorème du ressort de Tutte stipule que tout graphe planaire 3-connexe peut être dessiné dans un plan sans croisement de sorte que ses arêtes soient des segments de droite et que la face extérieure soit un polygone convexe. On l'appelle ainsi parce qu'un tel plongement peut être obtenu comme position d'équilibre d'un système de ressorts représentant les bords du graphe.

Le théorème de Steinitz stipule que tout graphe planaire 3-connexe peut être représenté par les arêtes d'un polyèdre convexe dans un espace tridimensionnel. Un plongement plan en ligne droite de $G,$ du type décrit par le théorème de Tutte, peut être formé en projetant une telle représentation polyédrique sur un plan.

Le théorème d'empilement de cercles stipule que tout graphe planaire simple peut être représenté comme le graphe d'intersection d'un empilement de cercles. Placer chaque sommet du graphe au centre du cercle correspondant conduit à une représentation en ligne droite du graphe. 

Heiko Harborth a soulevé la question de savoir si tout graphe planaire possède une représentation en ligne droite dans laquelle toutes les arêtes ont des longueurs entières, problème qui reste à l'état de conjecture, mais on sait que des plongements en ligne droite à distances entières existent pour les graphes cubiques.

Voir aussi

• Minimisation des courbures

Lien externe

• Théophile Trunc, Graphes planaires, paragraphe 2.3

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fáry's theorem » (voir la liste des auteurs).