Graphe planaire extérieur

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 le plan sans croisements des arêtes, 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 graphe G 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].

Un graphe planaire extérieur maximal, muni d'une 3-coloration.

Historique

Les graphes planaires extérieurs furent étudiés et nommés en 1967 par Gary Chartrand (en) et Frank Harary[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 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 dié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 s'il ne contient pas de subdivision du graphe complet K4 ou du graphe biparti complet K2,3[3]. De même, un graphe est planaire extérieur si et seulement s'il ne contient ni K4, ni K2,3 comme mineur, c'est-à-dire comme graphe obtenu en contractant et en supprimant des arêtes[4].

Un graphe sans triangle est planaire extérieur si et seulement s'il ne contient pas de subdivision de K2,3[5].

Biconnexité et hamiltonicité

Un graphe planaire extérieur est biconnexe 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 s'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, 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, c'est-à-dire que pour chaque sommet s et pour 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].

Coloration

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 trouvée en 1978 par Steve Fisk[9]. Une telle coloration peut être trouvée 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]. Une coloration utilisant le nombre optimal de couleurs peut être trouvée 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. 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[11], et est évidemment planaire. Cependant, les réciproques sont fausses : le graphe complet K4 est planaire, mais n'est ni série-parallèle, ni planaire extérieur ; le graphe biparti complet K2,3 est planaire et série-parallèle, mais n'est pas planaire extérieur. Toutes les forêts et tous les graphes cactus 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 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 s'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 d'un ensemble de cordes d'un cercle[16].

Autres propriétés

Les graphes planaires extérieurs ont une dégénérescence 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
  1. Felsner 2004.
  2. Chartrand et Harary 1967
  3. Chartrand et Harary 1967 ; Sysło 1979 ; Brandstädt, Le et Spinrad 1999, proposition 7.3.1, p. 117 ;Felsner 2004.
  4. Diestel.
  5. Sysło 1979.
  6. Chartrand et Harary 1967 ;Sysło 1979.
  7. Li, Corneil et Mendelsohn 2000, proposition 2.5.
  8. Proskurowski et Sysło 1986.
  9. Fisk 1978
  10. Fiorini 1975.
  11. Brandstädt, Le et Spinrad 1999, p. 174.
  12. Brandstädt, Le et Spinrad 1999, p. 169.
  13. Sysło et Proskurowski 1983.
  14. Kane et Basu 1976 ; Sysło 1979.
  15. El-Gindy 1985 ; Lin et Skiena 1995 ; Brandstädt, Le et Spinrad 1999, théorème 4.10.3, p. 65.
  16. Wessel et Pöschel 1985 ;Unger 1988.
  17. Lick et White 1970.
  18. Baker 1994.
  19. Scheinerman 1984 ;Brandstädt, Le et Spinrad 1999, p. 54.

Références


  • (en) Brenda S. Baker, « Approximation algorithms for NP-complete problems on planar graphs », Journal of the ACM, vol. 41, no 1,‎ , p. 153–180.
  • (en) Andreas Brandstädt, Van Bang Le et Jeremy Spinrad, Graph Classes : A Survey, Philadelphie, SIAM Monographs on Discrete Mathematics and Applications, , poche (ISBN 978-0-89871-432-6).
  • (en) Gary Chartrand et Frank Harary, « Planar permutation graphs », Annales de l'institut Henri Poincaré (B) Probabilités et Statistiques, vol. 3, no 4,‎ , p. 433–438 (lire en ligne).
  • (en) Reinhard Diestel, Graph Theory [détail des éditions], p. 107.
  • (en) H. El-Gindy, Hierarchical decomposition of polygons with applications, McGill University, coll. « Ph.D. thesis », . As cited by Brandstädt, Le et Spinrad 1999.
  • (en) Stefan Felsner, Geometric graphs and arrangements : some chapters from combinational geometry, Vieweg+Teubner Verlag, (ISBN 978-3-528-06972-8), p. 6.
  • (en) Stanley Fiorini, « On the chromatic index of outerplanar graphs », Journal of Combinatorial Theory, Series B, vol. 18, no 1,‎ , p. 35–38 (DOI 10.1016/0095-8956(75)90060-X).
  • (en) Steve Fisk, « A short proof of Chvátal's watchman theorem », Journal of Combinatorial Theory, Series B, vol. 24,‎ , p. 374 (DOI 10.1016/0095-8956(78)90059-X).
  • (en) Herbert Fleischner, D. P. Geller et Frank Harary, « Outerplanar graphs and weak duals », Journal of the Indian Mathematical Society, vol. 38,‎ , p. 215–219 (Math Reviews 0389672).
  • (en) Vinay G. Kane et Sanat K. Basu, « On the depth of a planar graph », Discrete Mathematics, vol. 14, no 1,‎ , p. 63–67 (DOI 10.1016/0012-365X(76)90006-6).
  • (en) Ming-Chu Li, Derek G. Corneil et Eric Mendelsohn, « Pancyclicity and NP-completeness in planar graphs », Discrete Applied Mathematics, vol. 98, no 3,‎ , p. 219–225 (DOI 10.1016/S0166-218X(99)00163-8).
  • (en) Don R. Lick et Arthur T. White, « k-degenerate graphs », Canadian Journal of Mathematics, vol. 22,‎ , p. 1082–1096 (lire en ligne).
  • (en) Yaw-Ling Lin et Steven S. Skiena, « Complexity aspects of visibility graphs », International Journal of Computational Geometry and Applications, vol. 5, no 3,‎ , p. 289–312 (DOI 10.1142/S0218195995000179).
  • (en) Andrzej Proskurowski et Maciej M. Sysło, « Efficient vertex-and edge-coloring of outerplanar graphs », SIAM Journal on Algebraic and Discrete Methods, vol. 7,‎ , p. 131–136 (DOI 10.1137/0607016).
  • (en) E. R. Scheinerman, Intersection Classes and Multiple Intersection Parameters of a Graph, Princeton University, coll. « Ph.D. thesis », (cité par Brandstädt, Le et Spinrad 1999).
  • (en) Maciej M. Sysło, « Characterizations of outerplanar graphs », Discrete Mathematics, vol. 26, no 1,‎ , p. 47–53 (DOI 10.1016/0012-365X(79)90060-8).
  • (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, coll. « Lecture Notes in Mathematics », , 248–256 p. (DOI 10.1007/BFb0071635).
  • (en) Walter Unger, Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), vol. 294, Springer-Verlag, coll. « Lecture Notes in Computer Science », , 61–72 p. (DOI 10.1007/BFb0035832).
  • (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, coll. « Teubner-Texte zur Mathematik », , 207–210 p. (cité par Unger 1988).

Voir aussi

Liens externes
  • Portail de la géométrie
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.