Test de planarité gauche-droite
En théorie des graphes, et en algorithmique, le test de planarité gauche-droite, aussi appelé critère de planarité de Fraysseix-Rosenstiehl 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. 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. Dans une comparaison pratique de six algorithmes de test de planarité réalisée en 2003 , il s'agissait alors de l'un des algorithmes testés les plus rapides.

Arêtes similaires et opposées 
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 ).  

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.

Caractérisation 

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

 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.
 On forme ensuite un graphe auxiliaire qui a un sommet pour chaque composante connexe formé d'arêtes similaires et une arête pour chaque paire d'arêtes opposées.
 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é 
 Critère de planarité de Whitney

Graphe planaire
Combinatoire