Planarité

La planarité est un concept mathématique qui concerne la représentation des graphes dans le plan. Un graphe est dit planaire s'il peut être dessiné de telle manière que ses arcs ne se croisent pas.

Pour déterminer si un graphe est planaire, on utilise généralement l'algorithme de Hopcroft-Tarjan ou celui de Boyer-Myrvold. Ces algorithmes permettent de tester rapidement la planarité d'un graphe en temps linéaire.

Un résultat important lié à la planarité est le théorème de Kuratowski, qui stipule qu'un graphe est planaire si et seulement s'il ne contient pas de sous-graphe homéomorphe à K5 (le graphe complet à 5 sommets) ou K3,3 (le graphe biparti complet avec 3 sommets dans chaque partition).

La planarité a des applications pratiques, notamment en électronique pour l'agencement des circuits imprimés, ou en géographie pour la représentation des cartes routières sans intersections.