Test de planarité gauche-droite

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 ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ 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 ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ 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 ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ sont similaires.

Figure 2. Les arêtes ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ sont opposées.

Figure 3. Les arêtes ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ sont opposées.

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 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é.

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

• Critère de planarité de Whitney