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
[modifier | modifier le code]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
[modifier | modifier le code]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
[modifier | modifier le code]-
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.
Notes et références
[modifier | modifier le code]- (en) Jonathan L. Gross et Thomas W. Tucker, Topological Graph Theory, Courier Corporation, (ISBN 978-0-486-41741-7, lire en ligne), p. 26
- (en) Carsten Thomassen, « The graph genus problem is NP-complete », Journal of Algorithms, vol. 10, no 4, , p. 568–576 (ISSN 0196-6774, DOI 10.1016/0196-6774(89)95006-0, lire en ligne, consulté le )
- (en) Bojan Mohar, « A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface », SIAM Journal on Discrete Mathematics, vol. 12, no 1, , p. 6–26 (ISSN 0895-4801 et 1095-7146, DOI 10.1137/S089548019529248X, lire en ligne, consulté le )
