Graphe planaire extérieur

Un graphe planaire extérieur maximal, muni d'un 3-coloriage.

En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans leplan sans croisements, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes. On démontre qu'un grapheG est planaire extérieur si et seulement si le graphe formé en ajoutant à G un nouveau sommet et toutes les arêtes le reliant aux sommets de G est un graphe planaire^[1].

Historique

Les graphes planaires extérieurs furent étudiés et nommés en 1967 par Gary Chartrand (en) et Frank Harary (en)^[2], en relation avec le problème de déterminer la planarité de graphes formés à l'aide d'un couplage parfait entre deux copies d'un graphe donné (par exemple, beaucoup des graphes de Petersen généralisés (en) sont formés de cette manière à partir d'un cycle). Ils démontrèrent que lorsque le graphe de base est biconnexe (c'est-à-dire lorsque la suppression d'un sommet quelconque laisse le graphe connecté), le graphe ainsi construit est planaire si et seulement si le graphe de base est planaire extérieur et le couplage forme une permutation dihédrale de son cycle extérieur.

Caractérisations par graphes exclus

Les graphes planaires extérieurs possèdent des caractérisations par graphes exclus analogues à celles des graphes planaires données par les théorèmes de Kuratowski et de Wagner : un graphe est planaire extérieur si et seulement si il ne contient pas de subdivision (en) du graphe complet K₄ ou du graphe biparti complet K_2,3^[3]. De même, un graphe est planaire extérieur si et seulement si il ne contient ni K₄, ni K_2,3 comme mineur, c'est-à-dire comme graphe obtenu en contractant et en supprimant des arêtes^[4].

Un graphe sans triangles est planaire extérieur si et seulement si il ne contient pas de subdivision de K_2,3^[5].

Biconnectivité et hamiltonicité

Un graphe planaire extérieur est biconnexe (en) si et seulement si la face extérieure du graphe forme un cycle simple (sans répétition de sommets). Un graphe planaire extérieur est hamiltonien si et seulement si il est biconnexe ; dans ce cas, la face extérieure constitue l'unique cycle hamiltonien^[6]. Plus généralement, la taille du plus grand cycle d'un graphe planaire extérieur est le nombre de sommets de sa plus grande composante biconnexe (en), aussi, déterminer les cycles hamiltoniens ou même les plus longs cycles d'un graphe planaire extérieur peut être fait en temps proportionnel à la taille du graphe, alors que ce problème est NP-complet pour des graphes arbitraires.

Les graphes planaires extérieurs maximaux satisfont à une condition plus forte que d'être hamiltoniens : ils sont pancycliques (en), c'est-à-dire que pour chaque sommet spour chaque k allant de trois au nombre de sommets du graphe, il existe un cycle de longueur k contenant s. Un cycle de cette longueur peut être obtenu en retirant successivement des triangles connectés au reste du graphe par une seule arête, le sommet retiré n'étant pas s, jusqu'à ce que la face externe du graphe restant soit un cycle de longueur k^[7].

Un graphe planaire est planaire extérieur si et seulement si chacune de ses composantes biconnexes est planaire extérieure^[5].

Coloriages

Tous les graphes (simples) planaires extérieurs peuvent être colorés en n'utilisant que trois couleurs^[8]  ; ce résultat joue un rôle essentiel dans la solution simplifiée du problème du musée (en) trouvée en 1978 par Steve Fisk^[9]. Un tel coloriage peut être trouvé en temps linéaire (proportionnel au nombre de sommets du graphe) par un algorithme glouton consistant à retirer un sommet quelconque de degré au plus deux (il en existe toujours au moins un si le graphe est planaire extérieur), colorer le graphe restant (en utilisant récursivement le même algorithme), et à colorer le sommet retiré en utilisant une couleur différente de celle de ses deux voisins.

D'après le théorème de Vizing, l'indice chromatique de tout graphe (le nombre minimal de couleurs nécessaires pour colorer ses arêtes) est soit le degré maximum de ses sommets, soit 1 + ce degré maximum. Dans le cas d'un graphe planaire extérieur, on est toujours dans le premier cas, sauf lorsque le graphe est un cycle de longueur impaire^[10]. Un coloriage utilisant le nombre optimal de couleurs peut être trouvé en temps linéaire à l'aide d'un algorithme de parcours en largeur de l'arbre dual du graphe^[8].

Familles de graphes associées

Un graphe cactus (en). Les cactus forment une sous-classe des graphes planaires extérieurs.

Tout graphe planaire extérieur est un sous-graphe d'un graphe série-parallèle (en)^[11], et est évidemment planaire. Cependant, les réciproques sont fausses : le graphe complet K₄ est planaire, mais n'est ni série-parallèle, ni planaire extérieur ; le graphe biparti complet K_2,3 est planaire et série-parallèle, mais n'est pas planaire extérieur. Toutes les forêts et tous les graphes cactus (en) sont planaires extérieurs^[12].

Le graphe dual (faible) d'un graphe planaire extérieur plongé dans le plan (le graphe ayant un sommet pour chaque face bornée du plongement, et une arête pour chaque paire de faces adjacentes) est une forêt, et le graphe dual d'un graphe de Halin (en) est un graphe planaire extérieur. Un graphe planaire est planaire extérieur si et seulement si son dual (faible) est une forêt, et est un graphe de Halin si et seulement si son dual faible est biconnexe et planaire extérieur^[13].

Un plongement planaire est dit k-planaire extérieur si supprimer les sommets de la face externe résulte en un plongement (k − 1)-planaire extérieur ; pour que cette définition ait un sens, on ajoute que le seul plongement 0-planaire extérieur est le plongement vide, ou que le plongement qui définit les graphes planaires extérieurs est un plongement 1-planaire extérieur ; un graphe est k-planaire extérieur s'il possède un plongement k-planaire extérieur^[14].

Un graphe planaire extérieur maximal est un graphe planaire extérieur auquel on ne peut ajouter aucune arête sans détruire cette propriété. Tout graphe planaire extérieur maximal ayant n sommets a exactement 2n − 3 arêtes, et chacune de ses faces bornées est un triangle. Un graphe planaire extérieur est un graphe cordal si et seulement si il est maximal. Tout graphe planaire extérieur maximal est le graphe de visibilité (en) d'un polygone simple^[15].

Tout graphe planaire extérieur est un graphe circulaire (en), c'est-à-dire le graphe d'intersection (en) d'un ensemble de cordes d'un cercle^[16].

Autres propriétés

Les graphes planaires extérieurs ont une dégénérescence (en) au plus égale à deux : tout sous-graphe contient un sommet de degré au plus deux^[17].

Ils ont également une largeur arborescente au plus égale à deux, ce qui a pour conséquence que de nombreux problèmes d'optimisation qui sont NP-complets pour des graphes arbitraires peuvent être résolus en temps polynomial par des méthodes de programmation dynamique lorsque les données sont des graphes planares extérieurs. Plus généralement, les graphes k-planaires extérieurs ont une largeur arborescente qui est un O(k)^[18].

Tout graphe planaire extérieur peut être représenté comme un graphe d'intersection de rectangles (d'axes parallèles), et donc sa boxicité (en) est au plus égale à deux^[19].

Notes

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Outerplanar graph » (voir la liste des auteurs)

• (en) Brenda S. Baker, « Approximation algorithms for NP-complete problems on planar graphs », dans Journal of the ACM, vol. 41, n^o 1, 1994, p. 153–180 .
• (en) Andreas Brandstädt, Van Bang Le et Jeremy Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999 (ISBN 0-89871-432-X) .
• (en) Gary Chartrand et Frank Harary, « Planar permutation graphs », dans Annales de l'institut Henri Poincaré (B) Probabilités et Statistiques, vol. 3, n^o 4, 1967, p. 433–438 [texte intégral] .
• (en) Reinhard Diestel, Graph Theory, vol. 173, Springer-Verlag, 2000 (ISBN 0387989765), p. 107 .
• (en) H. El-Gindy, Hierarchical decomposition of polygons with applications, McGill University, 1985 . As cited by Brandstädt, Le et Spinrad 1999.
• (en) Stefan Felsner, Geometric graphs and arrangements: some chapters from combinational geometry, Vieweg+Teubner Verlag, 2004 (ISBN 9783528069728), p. 6 .
• (en) Stanley Fiorini, « On the chromatic index of outerplanar graphs », dans Journal of Combinatorial Theory, Series B, vol. 18, n^o 1, 1975, p. 35–38 [lien DOI] .
• (en) Steve Fisk, « A short proof of Chvátal's watchman theorem », dans Journal of Combinatorial Theory, Series B, vol. 24, 1978, p. 374 [lien DOI] .
• (en) Herbert J. Fleischner, D. P. Geller et Frank Harary, « Outerplanar graphs and weak duals », dans Journal of the Indian Mathematical Society, vol. 38, 1974, p. 215–219 .
• (en) Vinay G. Kane et Sanat K. Basu, « On the depth of a planar graph », dans Discrete Mathematics, vol. 14, n^o 1, 1976, p. 63–67 [lien DOI] .
• (en) Ming-Chu Li, Derek G. Corneil et Eric Mendelsohn, « Pancyclicity and NP-completeness in planar graphs », dans Discrete Applied Mathematics, vol. 98, n^o 3, 2000, p. 219–225 [lien DOI] .
• (en) Don R. Lick et Arthur T. White, « k-degenerate graphs », dans Canadian Journal of Mathematics, vol. 22, 1970, p. 1082–1096 [texte intégral] .
• (en) Yaw-Ling Lin et Steven S. Skiena, « Complexity aspects of visibility graphs », dans International Journal of Computational Geometry and Applications, vol. 5, n^o 3, 1995, p. 289–312 [lien DOI] .
• (en) Andrzej Proskurowski et Maciej M. Sysło, « Efficient vertex-and edge-coloring of outerplanar graphs », dans SIAM Journal on Algebraic and Discrete Methods, vol. 7, 1986, p. 131–136 [lien DOI] .
• (en) E. R. Scheinerman, Intersection Classes and Multiple Intersection Parameters of a Graph, Princeton University, 1984  (cité par Brandstädt, Le et Spinrad 1999).
• (en) Maciej M. Sysło, « Characterizations of outerplanar graphs », dans Discrete Mathematics, vol. 26, n^o 1, 1979, p. 47–53 [lien DOI] .
• (en) Maciej M. Sysło et Andrzej Proskurowski, Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, vol. 1018, Springer-Verlag, 1983, « On Halin graphs », p. 248–256 .
• (en) Walter Unger, Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), vol. 294, Springer-Verlag, 1988, « On the k-colouring of circle-graphs », p. 61–72 .
• (en) W. Wessel et R. Pöschel, Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984, vol. 73, B.G. Teubner, 1985, « On circle graphs », p. 207–210  (cité par Unger 1988).

Voir aussi

• Graphe planaire

Liens externes

• Outerplanar graphs, Information System on Graph Classes and Their Inclusions
• (en) Eric W. Weisstein, « Outplanar Graph », MathWorld

• Portail de la géométrie