Graphe toroïdal

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un graphe plongé sur le tore de telle façon que les arêtes ne se coupent pas.

En mathématiques, et plus précisément en théorie des graphes, un graphe G est toroïdal s'il peut être plongé sur le tore, c'est-à-dire que les sommets du graphe peuvent être placés sur le tore de telle façon que les arêtes ne se coupent pas. En général dire qu'un graphe est toroïdal sous-entend également qu'il n'est pas planaire.

Exemples[modifier | modifier le code]

Le graphe de Heawood, le graphe complet K7 (et par conséquent K5 et K6), le graphe de Petersen (et par conséquent le graphe biparti complet K3,3, qui en est un mineur), les snarks de Blanuša[1] et toutes les échelles de Möbius sont toroïdaux. Plus généralement, tout graphe de nombre de croisement (en) égal à 1 est toroïdal. Certains graphes ayant un nombre de croisement supérieur sont également toroïdaux : ainsi, le graphe de Möbius-Kantor, de nombre de croisement 4, est toroïdal[2].

Propriétés[modifier | modifier le code]

Tout graphe toroïdal est de nombre chromatique inférieur ou égal à sept[3] ; le graphe complet K7 est un exemple où ce nombre vaut 7 exactement[4] ; tout graphe toroïdal sans triangle a un nombre chromatique inférieur ou égal à quatre[5].

Le théorème de Robertson-Seymour montre qu'on peut caractériser les graphes toroïdaux (ou planaires) par un ensemble fini de mineurs exclus (comme le théorème de Kuratowski le fait pour les graphes planaires), mais cet ensemble n'est pas encore déterminé ; en 2011, on sait seulement qu'il comporte plus de 16 000 graphes[6].

Aspects algorithmiques[modifier | modifier le code]

Les graphes toroïdaux peuvent être reconnus en temps polynomial[7] (par contre déterminer le genre d'un graphe est un problème NP-complet[8]).

Notes[modifier | modifier le code]

  1. Orbanić et al. 2004.
  2. Marušič et Pisanski 2000.
  3. Heawood 1890.
  4. Chartrand et Zhang 2008.
  5. Kronk et White 1972.
  6. Voir (en) J. Chambers, Hunting for torus obstructions, Department of Computer Science, University of Victoria,‎ 2002.
  7. (Filotti, Miller et Reif 1979)
  8. (Thomassen 1989)

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

  • (en) Gary Chartrand et Ping Zhang, Chromatic graph theory, CRC Press,‎ 2008 (ISBN 9781584888000).
  • (en) Toshiki Endo, « The pagenumber of toroidal graphs is at most seven », Discrete Mathematics, vol. 175, no 1–3,‎ 1997, p. 87–96 (DOI 10.1016/S0012-365X(96)00144-6).
  • (en) IS Filotti, Gary L Miller et John Reif, « On determining the genus of a graph in O (v O (g)) steps », dans Proceedings of the eleventh annual ACM symposium on Theory of computing,‎ 1979, p. 27-37
  • (en) Steven J. Gortler, Craig Gotsman et Dylan Thurston, « Discrete one-forms on meshes and applications to 3D mesh parameterization », Computer Aided Geometric Design, vol. 23, no 2,‎ 2006, p. 83–112 (DOI 10.1016/j.cagd.2005.05.002).
  • (en) P. J. Heawood, « Map colouring theorems », Quarterly J. Math. Oxford Ser., vol. 24,‎ 1890, p. 322–339.
  • (en) W. Kocay, D. Neilson et R. Szypowski, « Drawing graphs on the torus », Ars Combinatoria, vol. 59,‎ 2001, p. 259–277 (lire en ligne).
  • (en) Hudson V. Kronk et Arthur T. White, « A 4-color theorem for toroidal graphs », Proceedings of the American Mathematical Society, American Mathematical Society, vol. 34, no 1,‎ 1972, p. 83–86 (DOI 10.2307/2037902, JSTOR 2037902).
  • (en) Dragan Marušič et Tomaž Pisanski, « The remarkable generalized Petersen graph G(8,3) », Math. Slovaca, vol. 50,‎ 2000, p. 117–121 (lire en ligne).
  • (en) Eugene Neufeld et Wendy Myrvold, Practical toroidality testing (dans Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms),‎ 1997, 574–580 p. (lire en ligne).
  • (en) Alen Orbanić, Tomaž Pisanski, Milan Randić et Brigitte Servatius, « Blanuša double », Math. Commun., vol. 9, no 1,‎ 2004, p. 91–103.
  • Carsten Thomassen, « The graph genus problem is NP-complete », Journal of Algorithms, vol. 10, no 4,‎ 1989, p. 568-576