Test de planarité

En théorie des graphes, le problème du test de planarité est le problème algorithmique qui consiste à tester si un graphe donné est un graphe planaire (c'est-à-dire s'il peut être dessiné dans le plan sans intersection d'arêtes). Il s'agit d'un problème bien étudié en informatique pour lequel de nombreux algorithmes pratiques ont été donnés, souvent en décrivant de nouvelles structures de données. La plupart de ces méthodes fonctionnent en temps O(n) (temps linéaire), où n est le nombre d'arêtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal. La sortie d'un algorithme de test de planarité, plutôt que d'être simplement une valeur booléenne (le graphe est-il planaire, oui ou non ?), peut être un plongement du graphe dans le plan si le graphe est planaire, ou la donnée d'un obstacle à la planarité tel qu'un sous-graphe de Kuratowski s'il ne l'est pas.

Les algorithmes de test de planarité tirent généralement parti des théorèmes de la théorie des graphes qui caractérisent l'ensemble des graphes planaires en termes indépendants du dessin de graphes. Ces critères comprennent notamment :

Le théorème de Kuratowski selon lequel un graphe est planaire si et seulement s'il ne contient pas de sous-graphe qui est une subdivision de K₅ (le graphe complet sur cinq sommets) ou de K_3,3 (le « graphe d'utilité », un graphe biparti complet à six sommets, dont trois sont connectés à chacun des trois autres).
Le théorème de Wagner d'après lequel un graphe est planaire si et seulement s'il ne contient pas de mineur (sous-graphe d'une contraction) isomorphe à K₅ ou K_3,3.
Le critère de planarité de Fraysseix-Rosenstiehl, caractérisant les graphes planaires en termes d'un ordre gauche-droite des arêtes dans un arbre de recherche en profondeur.

Le critère de planarité de Fraysseix-Rosenstiehl peut être utilisé directement dans le cadre des algorithmes de test de planarité, tandis que les théorèmes de Kuratowski et Wagner sont des applications indirectes : si un algorithme peut trouver une copie de K₅ ou K_3,3 dans un graphe donné, cela prouve que le graphe d'entrée n'est pas planaire et il retourne sans calcul supplémentaire.

D'autres critères de planarité, qui caractérisent mathématiquement les graphes planaires mais sont moins centraux pour les algorithmes de test de planarité, comprennent :

le critère de planarité de Whitney selon lequel un graphe est planaire si et seulement si son matroïde graphique est également cographique,
le critère de planarité de Mac Lane caractérisant les graphes planaires par les bases de leurs espaces de cycles,
le théorème de Schnyder caractérisant les graphes planaires par la dimension d'ordre d'un ordre partiel associé, et
l'invariant de Colin de Verdière qui caractérise les graphes planaires comme les graphes dont l'invariant est au plus 3.

Algorithmes

Méthode d'addition de chemins

La méthode maintenant classique d'addition de chemins de Hopcroft et Tarjan été le premier algorithme de test de planarité en temps linéaire publié en 1974^[1]. Robert Cori a décrit l'historique et les principes de cet algorithme dans un article paru en 2014 dans le Bulletin de la société informatique de France^[2] où il mentionne l'activité française dans ce domaine à peu près à la même époque. Une implémentation des algorithmes de Hopcroft et Tarjan est fournie dans la Library of Efficient Data types and Algorithms (en) de Mehlhorn, Mutzel et Näher^[3]^,^[4]. En 2012, Taylor^[5] a étendu cet algorithme pour générer toutes les permutations d'ordre cyclique des arêtes pour les plongements planaires de composantes biconnexes.

Méthode d'addition de sommets

Les méthodes d'addition de sommets opèrent en maintenant une structure de données représentant les plongements possibles d'un sous-graphe induit du graphe donné, et en ajoutant les sommets un par un à cette structure de données. Ces méthodes ont commencé avec une méthode en O(n²) conçue par Lempel, Even et Cederbaum en 1967^[6]. Elle a été améliorée par Even et Tarjan^[7] en 1976, qui ont trouvé une solution en temps linéaire pour l'étape de numérotation st, et par Booth et Lueker^[8], qui ont développé la structure de données d'arbre PQ. Avec ces améliorations, l'algorithme est linéaire et surpasse la méthode d'addition de chemins dans la pratique^[9] . Cette méthode a également été étendue pour permettre un calcul efficace d'un plongement planaire (dessin) d'un graphe planaire^[10] . En 1999, Shih et Hsu ont simplifié ces méthodes en utilisant un arbre PC (une variante non enracinée des arbres PQ) et un parcours d'arbre postfixe de l'arbre de recherche en profondeur des sommets^[11].

Méthode d'addition d'arêtes

En 2004, John Boyer et Wendy Myrvold^[12] ont développé un algorithme simplifié en temps linéaire, inspiré à l'origine de la méthode de l'arbre PQ, qui se libère de l'arbre PQ et utilise des adjonctions d'arêtes pour calculer un plongement planaire, s'il existe. Sinon, une subdivision de Kuratowski (de K₅ ou K_3,3) est calculée. Il s'agit de l'un des deux algorithmes les plus récents (l'autre est l'algorithme de test de planarité de de Fraysseix, de Mendez et Rosenstiehl^[13]). Le test de Boyer-Myrvold a été étendu pour extraire plusieurs subdivisions de Kuratowski d'un graphe d'entrée non planaire en un temps d'exécution linéairement dépendant de la taille de sortie^[14]. Le code source du test de planarité^[15]^,^[16] et de l'extraction des subdivisions de Kuratowski est public. Un autre algorithme est donné par Bernhard Haeupler et Robert E. Tarjan^[17]. D'autres algorithmes qui localisent un sous-graphe de Kuratowski en temps linéaire ont été développés par Williamson dans les années 1980^[18].

Méthode de séquence de construction

Une méthode différente utilise une construction inductive de graphes 3-connexes pour construire de façon incrémentale des plongements planaires de chaque composante 3-connexe du graphe donné (et donc un plongement planaire du graphe lui-même)^[19]. La construction commence par K₄ et est définie de telle manière que chaque graphe intermédiaire vers une composante complète est à nouveau 3-connexe. Étant donné que ces graphes ont un plongement unique (au retournement et au choix de la face externe près), le graphe suivant, s'il est toujours planaire, doit être un raffinement du graphe précédent. Cela permet de réduire le test de planéité au test, à chaque étape, si l'arête suivante ajoutée a ses deux extrémités sur la face externe du plongement courant. Bien que conceptuellement très simple (et en temps linéaire), la méthode elle-même est compliquée par la difficulté de trouver la séquence de construction.

Variantes et extensions

La recherche continue à être active sur des variantes, concernant à la fois la parallélisation et la distribution sur plusieurs sites, et sur des familles particulières de graphes; voici un échantillon :

Giuseppe Liotta, Ignaz Rutter et Alessandra Tappini, « Simultaneous FPQ-Ordering and Hybrid Planarity Testing », SOFSEM,‎ 2020, p. 617-626.
Seok-Hee Hong et Hiroshi Nagamochi, « A linear-time algorithm for testing full outer-2-planarity », Discret. Appl. Math., vol. 255,‎ 2019, p. 234-257.
Guy Barshap et Tamir Tassa, « Privacy-Preserving Planarity Testing of Distributed Graphs », Trans. Data Priv., vol. 12, n^o 2,‎ 2019, p. 117-144.

Un autre sujet est la variante dynamique des algorithmes : tester la planarité d'un graphe qui évolue par adjonction et suppression de sommets ou d'arêtes : Étant donné un graphe dynamique, sujet à des insertions et des suppressions d'arêtes, la question est de savoir si le graphe admet couramment une représentation planaire. Les auteurs donnent un algorithme déterministe entièrement dynamique pour les graphes généraux, fonctionnant en temps amorti $O(log^{3}n)$ par insertion ou suppression d'arêtes, qui maintient un bit indiquant si le graphe est actuellement planaire ou non. C'est une amélioration du meilleur algorithme précédent, de 1996, et dû à Eppstein, Galil, Italiano, Spencer qui demande un temps $O({\sqrt {n}})$ amorti par mise à jour.

David Eppstein, Zvi Galil, Giuseppe F. Italiano et Thomas H. Spencer, « Separator Based Sparsification: I. Planarity Testing and Minimum Spanning Trees », Journal of Computer and Systems Sciences, vol. 52, n^o 1,‎ 1996, p. 3-27

Zvi Galil, Giuseppe F. Italiano et Neil Sarnak, « Fully Dynamic Planarity Testing with Applications », Journal of the ACM, vol. 46, n^o 1,‎ 1999, p. 28-91
Jacob Holm et Eva Rotenberg, « Fully-dynamic planarity testing in polylogarithmic time », STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing,‎ 2020, p. 167–180 (DOI 10.1145/3357713.3384249)

Une présentation est donnée dans Quanta Magazine^[20]