Critère de planarité de Mac Lane

Un article de Wikipédia, l'encyclopédie libre.

En théorie des graphes, le critère de planarité de Mac Lane est une caractérisation des graphes planaires par leur espaces de cycles (en), nommée d'après Saunders Mac Lane qui l'a publiée en 1937. Le critère dit qu'un graphe est planaire si et seulement si son espace de cycles (pris modulo 2) possède une base de cycles (en) dans laquelle chaque arête du graphe contribue à au plus deux vecteurs de la base.

Description[modifier | modifier le code]

À tout cycle c d'un graphe G à m arêtes, on peut associer une vecteur de dimension m à coefficients 0 et 1 qui a une coordonnée égale à 1 dans les positions des arêtes du cycle c et 0 dans les autres positions. L'espace des cycles C(G) du graphe est l'espace vectoriel formé des combinaisons linéaires de ces vecteurs. Dans la caractérisation de Mac Lane, C(G) est un espace vectoriel sur le corps fini GF(2) à deux éléments ; dans cet espace vectoriel, les vecteurs sont additionnés coordonnées par coordonnées modulo 2. Une 2-base de G est une base de C(G) avec la propriété que, pour toute arête e de G, au plus deux vecteurs de la base ont des valeurs non nulles dans la position correspondant à e. Avec ces définitions, la caractérisation de Mac Lane s'énonce plus formellement en : les graphes planaires sont exactement les graphes qui possèdent une 2-base.

Une 2-base existe pour les graphes planaires[modifier | modifier le code]

Une direction de la caractérisation dit que chaque graphe planaire possède une 2-base. Une telle base peut être trouvée comme la collection des contours des faces finies d'un plongement planaire du graphe donné G.

Une arête qui est un isthme de G apparaît deux fois sur le contour d'une même et unique face et a donc une coordonnée nulle dans le vecteur correspondant. Ainsi, les seules arêtes qui ont des coordonnées non nulles sont celles qui séparent deux faces différentes ; ces arêtes apparaissent soit une fois (si l'une des faces n'est pas finie), soit deux fois dans la collection des contours des faces finies.

Il reste à prouver que ces cycles constituent une base. Une façon de le prouver est par l'induction. Comme cas de base, si G est un arbre, alors il n'a pas de faces bornée et C(G) est de dimension zéro et a une base vide. Sinon, la suppression d'une arête de la face infini de G réduit à la fois d'une unité la dimension de l'espace des cycles et le nombre de faces finies, et l'induction s'ensuit.

Il est également possible d'utiliser la formule d'Euler pour montrer que le nombre de cycles dans cette collection est égal au nombre cyclomatique qui est par définition la dimension de l'espace des cycles. Chaque sous-ensemble non vide de cycles a une somme vectorielle qui représente le contour de l'union des faces finies dans le sous-ensemble, qui ne peut pas être vide (l'union comprend au moins une face finie et exclut la face infinie, il doit donc y avoir des arêtes qui les séparent). Par conséquent, il n'existe pas de sous-ensemble de cycles dont la somme des vecteurs est égale à zéro, ce qui signifie que tous les cycles sont linéairement indépendants. En tant qu'ensemble linéairement indépendant de la même taille que la dimension de l'espace, cette collection de cycles doit constituer une base.

Le graphe est planaire quand une 2-base existe[modifier | modifier le code]

O'Neil 1973 donne le raisonnement simple suivant pour l'autre sens de la caractérisation, basé sur la caractérisation des graphes planaires par le théorème de Robertson-Seymour et la caractérisation des graphes planaires par Mineur.

O'Neill observe que la propriété de posséder une 2-base est préservé par passage aux mineurs : si on contracte une arête, la même contraction peut être réalisée sur les vecteurs de la base, si on supprime une arête qui a une coordonnée non nulle dans un seul vecteur de la base, ce vecteur peut être supprimé de la base, et s'il a une coordonnée non nulle dans deux vecteurs de la base, les deux vecteurs peuvent être remplacés par leur somme modulo 2.

Maintenant, si C(G) est une base de cycles pour un graphe arbitraire, elle doit couvrir quelques arêtes exactement une fois car sinon la somme des vecteurs serait nulle, ce qui est impossible pour une base, et donc C(G) peut être augmenté par un cycle supplémentaire formé de ces arêtes couvertes une fois seulement, tout en préservant la propriété que toute arête est couverte au plus deux fois. Le graphe complet K5 ne possède pas de 2-base : C(G) a dimension 6, tout vecteur non nul de C(G) a des coordonnées non nulles pour au moins trois arêtes, et donc toute base augmentée aurait au moins 21 éléments, ce qui excède les 20 vecteurs non nuls possibles si chacune des dix arêtes était non nulle dans au plus deux vecteurs de base. Un raisonnement similaire montre qui le graphe biparti complet K3,3 ne possède pas de 2-base : C(G) a dimension 4, et tout vecteur non trivial de C(G) a au moins 4 coordonnées non nulles, de sorte que la base augmentée aurait au moins 20 éléments non nuls, , ce qui excède les 18 vecteurs non nuls possibles si chacune des dix arêtes était non nulle dans au plus deux vecteurs de base. Comme la propriété de posséder une 2-base est conservée par passage au mineurs et est fausse pour les deux graphes non planaires minimaux au sens des mineurs, à savoir K5 et K3,3, il n'est pas non plus vrai pour tout autre graphe non planaire.

(Lefschetz 1965) donne une autre démonstration, basée sur des arguments de topologie algébrique. Il utilise une formulation légèrement différente du critère de planarité, selon lequel un graphe est planaire si et seulement s'il comporte un ensemble de cycles (pas nécessairement simples) couvrant chaque arête exactement deux fois, de sorte que la seule relation non triviale entre ces cycles dans C(G) est que leur somme soit nulle. Si tel est le cas, le fait de supprimer l'un des cycles donne une base qui satisfait encore le critère de Mac Lane. Si un graphique planaire est plongé dans une sphère, les cycles de ses faces satisfont clairement la propriété de Lefschetz. Inversement, comme le montre Lefschetz, lorsqu'un graphe G possède un ensemble de cycles ayant cette propriété, ils forment nécessairement les cycles des faces d'un plongement du graphe sur la sphère.

Application[modifier | modifier le code]

(Ja'Ja' et Simon 1982) utilisent le critère de planarité de Mac Lane dans un algorithme parallèle de test de planarité et de construction de représentations planaires. Leur algorithme partitionne le graphe en composantes triconnexes ; chaque composante admet une représentation planaire unique (au choix de l'orientation de la face externe près) et on peut supposer que les cycles de la 2-base sont les cycles périphériques (en) du graphe.

Ja'Ja' et Simon partent d'une base de cycle fondamentale du graphe (une base de cycle générée à partir d'un arbre couvrant en formant un cycle pour chaque combinaison possible d'une chaîne dans l'arbre et d'une arête extérieure à l'arbre) et la transforment en une 2-base de cycles périphériques. Ces cycles forment les faces d'un plongement planaire du graphe donné.

Le critère de planéité de Mac Lane permet de compter facilement le nombre de cycles de faces finies dans un graphe planaire, comme le nombre cyclomatique du graphe. Cette propriété est utilisée pour définir le coefficient de maillage (en) du graphe, une variante normalisée du nombre de cycles de faces finies calculée en divisant le nombre cyclomatique par 2n − 5, qui est le nombre maximum possible de faces fermées d'un graphe planaire avec le même ensemble de sommets (Buhl et al. 2004).

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Mac Lane's planarity criterion » (voir la liste des auteurs).

Références[modifier | modifier le code]

Articles liés[modifier | modifier le code]

  • [Fulek Tóth 2020] Radoslav Fulek et Csaba D. Tóth, « Atomic embeddability, clustered planarity, and thickenability », Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,‎ , p. 2876-2895.
  • [Holm Rotenberg 2020] Jacob Holm et Eva Rotenberg, « Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity », Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,‎ , p. 2378-2397
  • [Eppstein 2019] David Eppstein, « Cubic planar graphs that cannot be drawn on few lines », arXiv,‎ (arXiv 1903.05256)



Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Critère_de_planarité_de_Mac_Lane&oldid=202350655 ».