Théorie topologique des graphes

À un graphe non orienté donné, on peut associer un espace topologique ainsi : chaque sommet est représenté par un point, et chaque arête est un arc homéomorphe à ${\displaystyle [0,1]}$qui relie ses deux extrémités[1]. Avec ce point de vue, on peut définir la notion d'homéomorphisme de graphe découlant directement de celle d'homéomorphisme topologique. De plus la notion de graphe connexe coïncide avec la connexité topologique et un graphe connexe est un arbre si et seulement si son groupe fondamental est trivial.

John Hopcroft et Robert Tarjan[2] ont inventé un algorithme pour tester la planarité d'un graphe en temps linéaire en le nombre d'arêtes. Un test de planarité efficace est un outil fondamental pour le tracé des graphes.

Fan Chung et al.[3] ont étudié le problème du plongement d'un graphe dans un livre, en tant qu'espace topologique constitué de feuilles ayant un bord commun, de sorte que les sommets du graphe soient dans ce bord commun. Ses arêtes sont dessinées sur des pages séparées de telle sorte que les arêtes plongées sur une même page ne se croisent pas. Ce problème apparait notamment en pratique lors du routage de cartes de circuits imprimés multicouches.

Parmi les grands résultats de la théorie topologique des graphes, le théorème des quatre couleurs est l'un des plus célèbres : il affirme que tout graphe planaire dont on veut distinguer chaque partie n'a besoin que de 4 couleurs (deux zones contiguës ne sont jamais de la même couleur). Une généralisation de ce théorème est la conjecture de Heawood, qui étend ce résultat à d'autres surfaces.

Les plongements de graphes sont également utilisés pour démontrer des résultats structurels sur les graphes, via entre autres la théorie des graphes mineurs ou le théorème de structure des graphes.

• Théorie des graphes
• Graphique planaire
• Graphique toroïdal
• Coloration de graphe
• Conjecture de Heawood
• Théorème des quatre couleurs
• Caractéristique d'Euler et genre
• Mineur (théorie des graphes)
• Graphe dual