Graphe planaire extérieur

vignette|Un graphe planaire extérieur maximal, muni d'une 3-coloration. 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. Les graphes planaires extérieurs furent étudiés et nommés en 1967 par et Frank Harary, 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. 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. 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. Un graphe sans triangle est planaire extérieur si et seulement s'il ne contient pas de subdivision de K2,3. 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).