Graphe planaire extérieur
# 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.

## Historique

Les graphes planaires extérieurs furent étudiés et nommés en 1967 par Gary Chartrand (en) 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.

## 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 $K_4$ ou du graphe biparti complet $K_{2,3}.$ De même, un graphe est planaire extérieur si et seulement s'il ne contient ni $K_4,$ ni $K_{2,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 $K_{2,3}.$

## 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. 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.

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

## Coloration

Tous les graphes (simples) planaires extérieurs peuvent être colorés en n'utilisant que trois couleurs ; 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. 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. 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.

## Familles de graphes associées

Tout graphe planaire extérieur est un sous-graphe d'un graphe série-parallèle, et est évidemment planaire. Cependant, les réciproques sont fausses : le graphe complet $K_4$ 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 sont planaires extérieurs.

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.

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.

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.

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.

## 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.

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).

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.

