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

Résumé
Contexte

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.

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

Caractérisation

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

Bibliographie complémentaire

Article lié

Wikiwand - on

Seamless Wikipedia browsing. On steroids.