Caractérisation des graphes planaires

Preuve d'un théorème de Jordan simplifié

TBD suffisant pour les graphes où les sommets sont dénombrables. TBD si courbe alors polygone alors droites TBD Diesel théorème 4.1.1 (p83 et suivantes) TBD https://minerve.ens-rennes.fr/images/Le_Théorème_de_Jordan_S.Quayle_V.Le_Gruiec..pdf TBD - topologie et courbe fermée Jordan : https://pagesperso.g-scop.grenoble-inp.fr/~lazarusf/Enseignement/graphesPlans.pdf

Mineurs

La caractérisation des graphes planaire se fait par "mineur exclu". C'est à dire caractériser les graphes qui vont nous empêcher de réussir un dessin planaire

En deux mots, les mineurs sont les graphes cachés dans un graphe plus gros :

La notion de mineur rend compte de l'intrication locale de chemins entre sommets. Ils ont donné lieu à un des plus joli théorème de théorie des graphes (et pourtant il y en a !), le théorème de Roberston-Seymour. Ce théorème indique en effet que :

• toute famille close par mineur peut être caractérisée par un nombre fini de mineurs exclu,
• Quelque soit le graphe $M$, il existe un algorithme en $\mathcal{O}(n^2)$ pour savoir si un graphe $G$ admet $M$ comme mineur.

En revanche, le théorème ne caractérise pas les algorithmes et ils ont une constante multiplicatives exponentielle en la taille du mineur à rechercher. Il n'est donc pas utilisé en pratique, mais la planarité fait partie de ces familles puisque :

On a déjà établi la proposition suivante :

Il nous reste à faire la réciproque. Initialement faire par Kuratowski en 1930 dans le cadre des subdivisions de graphes, il a été ré-ecrit par Wagner en 1937 avec les mineurs.

La caractérisation des graphes planaire est tres liée à la notion de 2-connexité. On va donc commencer par définir ce que c'est et démontrer des propriétés qui vont se révéler utiles en général et pour notre caractérisation en particulier.

2-connexité

Par exemple :

• un chemin est 1-connexe, si on supprime un sommet qui n'est pas une de ses extrémités on le déconnecte,
• un cycle est 2-connexe puisque supprimer un de ses sommets le transforme en chemin.

La $k$-connexité est bien une généralisation directe de la connexité puisqu'un graphe est connexe si et seulement si il est $1$-connexe.

Nous aurons uniquement besoin ici de la 2-connexité et de cette propriété en particulier :

Tout comme un graphe peut se décomposer en composantes connexes, on peut le décomposer en ses composantes 2-connexes

Trouver les composantes 2-connexes d'un graphe peut se faire linéairement en utilisant un DFS astucieux. C'est l'algorithme de Hopcroft et Tarjan (1973).

fonction DFS(u: Sommet, t: int, G: Graphe, 
             pos: *[]Sommet, pred: *[]Sommet, low: *[]Sommet, P: *Pile<(Sommet, Sommet)>) → [:]{Sommet}:

    pos[u] ← t
    low[u] ← t

    pour chaque voisin v de G[u]:
        si pos[v] == -1:                             # première fois que l'on voit v : uv est dans l'arbre
            pred[v] ← u
            P.empile((u, v))
            l ← DFS(v, t+1, G, &pos, &pred, &low, &P)

            low[u] ← min(low[u], low[v])             # mise à jour (1)

            si low[v] ≥ pos[u]:                      # on a trouvé une composante 2-connexe
                var s {Sommet} ← {}
                ajoute u et v à s

                (x, y) ← P.dépile()
                tant que (x, y) ≠ (u, v):
                    ajoute x et y à s
                    (x, y) ← P.dépile()
                
                ajoute s à la fin de l
        sinon si v ≠ pred[u]:                        # uv est un arc retour
            P.empile((u, v))
            low[u] ← min(low[u], pos[v])             # mise à jour (2)

    rendre l

algorithme 2_connexe(G: Graphe, r: Sommet):
    
    var pos []Sommet ← [-1 pour _ de [1 .. n]]
    var pred []Sommet ← [-1 pour _ de [1 .. n]]
    var low []Sommet ← [-1 pour _ de [1 .. n]]

    var P Pile<(Sommet, Sommet)> ← Pile<(Sommet, Sommet)>{}

    pred[r] ← r
    rendre DFS(r, 0, G, &pos, &pred, &low, &Pile)

Tout d'abord, il est clair que :

• le parcours est un DFS dont l'arbre associé est planté en $r$ et constitué des arêtes $\{ \{x, pred[x]\} \mid x \neq r\}$,
• la complexité totale de l'algorithme est en $\mathcal{O}(v(G) + e(G))$,
• toute arête du graphe est soit une arête de l'arbre soit une arête $xy$ avec $y$ sur le chemin entre $x$ et $r$ (on les appelle des arêtes retours)
• pos[x] est la distance entre $x$ et $r$ sur l'arbre du DFS

Commençons par caractériser les valeurs du tableau low :

La proposition précédente montre que le chemin allant de $x$ à l'élément $y$ sur le chemin allant de $x$ à $r$ tel que pos[y] = low[x] est dans la même composante 2-connexe puisqu'il existe un cycle élémentaire les reliant :

Utilisons cette propriété pour caractériser les composantes 2-connexes vis à vis d'un arbre DFS :

Comme il n'y a qu'au plus seul sommet commun entre deux composantes 2-connexes, les composantes 2-connexes reliées à $x$ comme nœud d'articulation vont s'organiser comme dans la figure suivante dans l'arbre de DFS :

Mais pour que deux sommets qu ne sont pas sur le même chemin jusqu'à la racine puissent être dans une même composante connexe, il faut qu'ils soient liée par au dessus de leur jonction, par exemple comme une de ces façons :

Il y en a d'autres, mais pour toutes on a low[s] < pos[s]. Ces éléments ne peuvent donc faire partie que d'une composante 2-connexe planté strictement plus haut que $s$. Pour un nœud d'articulation $x$ on peut affiner la représentation :

Seule la partie 2-connexe planté plus haut que $x$ peut être sur plusieurs branches, toutes les autres sont liées à $x$ par une seule arête. On a alors la proposition suivante qui fait fonctionner le tout :

La conséquence précédente nous montre que l'algorithme fonctionne, si low[v] ≥ pos[u] :

• $u$ est la racine d'une composante 2-connexe
• seul le successeur $v$ y est également

De là toutes les autres arêtes ajoutées et non encore supprimées après l'empilage de $(u, v)$ sont exactement toutes les arêtes de la composante 2-connexe.

En prenant l'exemple suivant :

On obtient l'arbre suivant (l'ordre de passage va de gauche à droite) :

L'algorithme est donc à la fois très rapide (il est linéaire en la taille du graphe) et montre des propriétés insoupçonnée du DFS.

En prenant l'exemple suivant :

• le chemin $afcb$ est une oreille du graphe restreint à $\{a, b, e\}$,
• le chemin $be$ est une oreille du graphe restreint au cycle $\{a, b, c, d, e\}$,
• le chemin $be$ n'est pas une oreille du graphe restreint à $\{a, b, c, d, e\}$.

Par exemple la figure ci-dessous montre une décomposition en oreilles :

On a commencé par le cycle noir, puis on a ajouté itérativement les chemins : vert, orange, violet, rouge et jaune.

Preuve de la réciproque

Commençons par nous restreindre aux graphes 2-connexes :

Nous allons prouver la réciproque par l'absurde en cherchant un graphe non planaire n'ayant ni $K_5$ ni $K_{3, 3}$ comme mineurs. On suppose qu'il en existe et on en considère un, disons $G^\star$ avec :

1. le nombre minimum de sommets : si on supprime un sommet de $G^\star$ il devient planaire
2. parmi tous ceux ayant un nombre minimum de sommets, notre graphe à un nombre minimum d'arêtes : si on supprime une arête de $G^\star$ il devient planaire

La proposition précédente nous montre alors que $G^\star$ est 2-connexe sinon il existerait une de ses composante 2-connexe non planaire et contredirait sa minimalité en nombre de sommets. De plus, tout sommet de $G^\star$ est de degré au moins 3 puisque :

• $G^\star$ est 2-connexe il ne peut donc avoir aucun sommet de degré 1 (supprimer son voisin déconnecterait le graphe),
• s'il existait un sommet de degré 2 on pourrait fusionner ses 2 arêtes et le graphe serait encore non planaire (et contredirait sa minimalité en nombre de sommets)

De là, toute décomposition en oreilles de $G^\star$ va contenir au moins un chemin dont on pourra supprimer une arête, disons $uv$ sans perdre la 2-connectivité du graphe. En revanche le graphe résultant $G^\star - uv$ sera planaire.

Comme $G^\star - uv$ est 2-connexe il existe des cycles élémentaires contenant $u$ et $v$. Notons $\mathcal{C}$ cet ensemble. Pour toute représentation planaire $P$ de $G^\star - uv$ on peut compter pour chaque cycle $C$ de $\mathcal{C}$ le nombre $N_P(C)$ de faces qu'il contient et on note $N(P) = \max(\{N_P(C) \mid C \in \mathcal{C}\})$. On choisi alors une représentation planaire $P^\star$ de $G^\star - uv$ qui réalise le maximum de $N(P)$ pour toutes les représentations planaires de $G^\star - uv$ et $C^\star$ un cycle de $\mathcal{C}$ tel que $N_{P^\star}(C^\star) = N(P^\star)$.

Le choix de $G^\star - uv$, $P^\star$ et de $C^\star$ implique plusieurs choses. Premièrement $u$ et $v$ ne sont pas voisins dans $C^\star$ (l'arête $uv$ n'est pas dans le graphe). De là, il n'existe pas d'oreille de $C^\star$ dont les 2 sommets d'accroche sont entre $u$ et $v$ et le chemin à l'extérieur de $C^\star$ :

Car il existerait un cycle (le cycle rouge) qui aurait au moins une région de plus que $C^\star$ ce qui est impossible :

On ne peut pas non plus ajouter l'arête $uv$ à $P^\star$ sans le rendre non planaire. Il existe donc deux oreilles reliant un arc entre $u$ et $v$ à l'autre, l'un interne (qui empêche de relier $u$ et $v$ par l'intérieur) l'autre externe (qui empêche de relier $u$ et $v$ par l'extérieur):

Examinons les différents cas possible. Tout d'abord pour que l'oreille extérieur ne soit pas d'un côté du cycle, il faut que ses accroches soient différentes de $u$ et $v$ :

Pour l'oreille interne, on regarde ses accroches. Si elles sont différentes de celles de l'oreille interne et de $u$ et $v$ on est dans le cas suivant :

Or ce cas admet $K_{3,3}$ comme mineur :

Si une des oreilles est différente il faut que le cycle intérieur soit attaché de l'intérieur sinon comme il n'y a pas d'oreille sur la même face, on pourrait sortir l'oreille interne :

Mais un seul ancrage ne suffit pas :

Et pour qu'on ne se retrouve pas dans le cas précédent, cela nous force à avoir un ancrage en $u$ ou $v$ :

Or ce cas admet $K_{3,3}$ comme mineur :

Il nous reste un dernier cas à vérifier, celui où les 2 ancrages sont les même. Il faut là aussi rajouter des attaches pour éviter de pouvoir le placer à l'extérieur :

Pour ne pas retomber dans les cas précédent on doit se retrouver dans cas suivant, les 2 nœuds blancs pouvant être identique :

La encore, ce cas admet un mineur interdit, $K_5$ :

On a examiné tous les cas, la réciproque est démontrée.