Un graphe non orienté est dit planaire quand on peut le représenter dans un plan sans qu'il y ait intersection d'arêtes.  Les graphes planaires apparaissent  lors de la segmentation d'une image, ils jouissent de propriétes remarquables : formule d'Euler, théorème des quatre couleurs et caractérisation de  Kuratowski.  Le sujet de TER est envisagé en deux parties. Une partie théorique dans laquelle les étudiants développeront les propriétés classiques des graphes planaires et une partie plus pratique dans laquelle ils implanteront l'algorithme proposé par Hoptcroft et Tarjan [ 1 ] pour résoudre le problème d'isomorphisme des graphes planaires.

[ 1 ] J. E. Hopcroft and R. E. Tarjan. A V 2 algorithm for determining isomorphism of planar graphs. Information Processing Letters, 1(1): 32--34, 1971.