Critère de planarité de Mac Lane
En théorie des graphes, le critère de planarité de Mac Lane est une caractérisation des graphes planaires par leur , 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  dans laquelle chaque arête du graphe contribue à au plus deux vecteurs de la base.

Description 
À tout cycle  d'un graphe  à  arêtes, on peut associer une vecteur de dimension  à coefficients 0 et 1 qui a une coordonnée égale à 1 dans les positions des arêtes  du cycle  et 0 dans les autres positions. L'espace des cycles  du graphe est l'espace vectoriel formé des combinaisons linéaires de ces vecteurs. Dans la caractérisation de Mac Lane,  est un espace vectoriel sur le corps fini   à deux éléments ; dans cet espace vectoriel, les vecteurs sont additionnés coordonnées par coordonnées modulo 2. Une 2-base  de  est une base de  avec la propriété que, pour toute arête  de , au plus deux vecteurs de la base ont des valeurs non nulles dans la position correspondant à . 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 
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é .

Une arête qui est un isthme de  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  est un arbre, alors il n'a pas de faces bornée et  est de dimension zéro et a une base vide. Sinon, la suppression d'une arête de la face infini de  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 
 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  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  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  ne possède pas de 2-base :  a dimension 6, tout vecteur non nul de   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  ne possède pas de 2-base :  a dimension 4, et tout vecteur non trivial de  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  et , il n'est pas non plus vrai pour tout autre graphe non planaire.

 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  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 
 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  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  du graphe, une variante normalisée du nombre de cycles de faces finies calculée en divisant le nombre cyclomatique par , qui est le nombre maximum possible de faces fermées  d'un graphe planaire avec le même ensemble de sommets ().

Notes et références

Références 
.
.
.
.
.

Articles liés 
.

 

Théorie algébrique des graphes
Graphe planaire