Plongement de graphe
En théorie topologique des graphes, un plongement de graphe sur une surface est, informellement, une façon de dessiner ce graphe sur cette surface sans que deux arêtes se croisent. Plus formellement, on peut définir un plongement d'un graphe vers une surface comme une fonction injective continue d'un espace topologique associé à ce graphe vers cette surface[1].
On appelle notamment graphe planaire un graphe qui peut être plongé sur le plan euclidien et graphe toroïdal un graphe qui peut être plongé sur un tore.
Terminologie
Le genre d'un graphe est l'entier minimal tel que le graphe peut être plongé sur une surface orientable de genre [2]. En particulier, les graphes planaires sont de genre 0 puisqu'ils peuvent être plongés sur une sphère.
Complexité algorithmique
Le problème du genre d'un graphe est NP-complet[2].
En revanche, pour une surface donnée, il est possible de trouver en temps linéaire un plongement d'un graphe dans cette surface s'il existe, ou dans le cas contraire d'identifier un sous-graphe homéomorphe à un sous-graphe minimal interdit pour la plongeabilité dans cette surface[3].
Exemples
-
Plongement du graphe de Petersen dans le plan projectif. -
Plongement du graphe de Pappus sur un tore. -
Le 24-graphe de Klein peut être plongé sur une surface orientable de genre 3.
