Critère de planarité de Mac Lane

À 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és 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 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.

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 K₅ 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 K_3,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 K₅ et K_3,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.

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