Test de planarité gauche-droite

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

En théorie des graphes, et en algorithmique, le test de planarité gauche-droite, aussi appelé critère de planarité de Fraysseix-Rosenstiehl[1] est une caractérisation des graphes planaires basée sur les propriétés des arbres de parcours en profondeur (encore appelés arbres de Trémaux), publiée par de Fraysseix et Rosenstiehl en 1982 et 1985[2],[3]. Ils ont ensuite utilisée cette caractérisation, avec Patrice Ossona de Mendez, pour développer un algorithme de test de planarité en temps linéaire[4],[5]. Dans une comparaison pratique de six algorithmes de test de planarité réalisée en 2003[6] , il s'agissait alors de l'un des algorithmes testés les plus rapides.

Arêtes similaires et opposées[modifier | modifier le code]

Dans toute recherche en profondeur d'un graphe G, les arêtes rencontrées lors de la découverte d'un sommet pour la première fois définissent un arbre de recherche en profondeur T de G. Un tel arbre est aussi appelé un arbre de Trémaux. Les arêtes restantes constituent par définition le coarbre : elles relient deux sommets tels que l'un soit ancêtre ou descendant de l'autre dans T. Les arêtes du coarbre s'appelle parfois arcs arrières (p. 2 dans [7]).

Quand on le graphe G dans le plan, deux arêtes du coarbre sont dites similaires si elles figurent du même côté dans T, elles sont opposées dans le cas contraire. Dans les figures suivantes, les cercles simples représentent des sommets, les cercles doubles représentent des sous-arbres, les segments torsadés représentent des chemins dans l'arbre T, et les arcs courbes représentent des arêtes du coarbre. La racine de chaque arbre figure au bas de la figure. Dans la Figure 1, les arêtes étiquetés et sont similaires pour T, ce qui signifie qu'aux extrémités les plus proches de la racine de l'arbre, elles seront toutes les deux du même côté de l'arbre dans tout dessin dans le plan. Dans les Figures 2 et 3, les arêtes avec les mêmes étiquettes et sont opposées pour T, ce qui signifie qu'elles se trouveront sur des côtés opposés de l'arbre dans chaque dessin dans le plan.

Figure 1. Les arêtes et sont similaires.
Figure 2. Les arêtes et sont opposées.
Figure 3. Les arêtes et sont opposées.

Caractérisation[modifier | modifier le code]

Théorème — Soit G un graphe et soit T un arbre de Trémaux de G. Le graphe G est planaire si et seulement s'il existe une partition des arêtes du coarbre de G en deux classes, de sorte que deux arêtes appartiennent à une même classe si elles sont du même côté de T et que deux arêtes appartiennent à des classes différentes si elles sont du côté opposé de T.

Cette caractérisation conduit à un test de planarité (mais qui est inefficace dans cette formulation) :

  1. On détermine, pour toutes les paires d'arêtes si elles sont du même côté ou de côtés opposés.
  2. On forme ensuite un graphe auxiliaire qui a un sommet pour chaque composante connexe[pas clair] formé d'arêtes similaires et une arête pour chaque paire d'arêtes opposées.
  3. Tester que ce graphe auxiliaire est biparti.

Rendre cet algorithme efficace consiste à trouver un sous-ensemble des paires similaires et opposés qui suffit pour effectuer cet algorithme sans devoir déterminer la relation entre toutes les paires d'arêtes du graphe donné.

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

  1. ↑ Christopher Auer, Andreas Gleißner, Kathrin Hanauer et Sebastian Vetter, « Testing planarity by switching trains », Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers, Berlin, Springer, vol. 7704,‎ , p. 557–558 (DOI 10.1007/978-3-642-36763-2_51).
  2. ↑ Hubert de Fraysseix et Pierre Rosenstiehl, « A depth-first-search characterization of planarity », Graph Theory (Cambridge, 1981), North-Holland, Amsterdam-New York,‎ , p. 75–80 (MR 671906).
  3. ↑ Hubert de Fraysseix et Pierre Rosenstiehl, « A characterization of planar graphs by Trémaux orders », Combinatorica, vol. 5, no 2,‎ , p. 127–135 (DOI 10.1007/BF02579375, MR 815578).
  4. ↑ Hubert de Fraysseix, Patrice Ossona de Mendez et Pierre Rosenstiehl, « Trémaux trees and planarity », International Journal of Foundations of Computer Science, vol. 17, no 5,‎ , p. 1017–1029 (DOI 10.1142/S0129054106004248, MR 2270949, arXiv math.CO/0610935).
  5. ↑ Hubert de Fraysseix et Patrice Ossona de Mendez, « Trémaux trees and planarity », European Journal of Combinatorics, vol. 33, no 3,‎ , p. 279–293 (DOI 10.1016/j.ejc.2011.09.012, MR 2864415, arXiv math/0610935).
  6. ↑ John M. Boyer, Pier Francesco Cortese, Maurizio Patrignani et Giuseppe Di Battista, « Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm », Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003, Revised Papers, Berlin, Springer,‎ , p. 25–36 (DOI 10.1007/978-3-540-24595-7_3, MR 2177580).
  7. ↑ Hubert De Fraysseix, Patrice Ossona De Mendez et Pierre Rosenstiehl, « Tr\'{e}maux trees and planarity », International Journal of Foundations of Computer Science, vol. 17, no 05,‎ , p. 1017–1029 (ISSN 0129-0541 et 1793-6373, DOI 10.1142/S0129054106004248, lire en ligne, consulté le )

Bibliographie complémentaire[modifier | modifier le code]

  • (de) Daniel Kaiser, Implementation und Animation des Links-Rechts-Planaritätstests : Bachelorarbeit, (Diplomarbeit) Université de Constance, FB Informatik und Informationswissenschaft, .

Article lié[modifier | modifier le code]

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Test_de_planarité_gauche-droite&oldid=204994334 ».