Conjecture de Scheinerman

En mathématiques, et notamment en théorie des graphes, la conjecture de Scheinerman, qui, maintenant qu'elle est démontrée, est un théorème, affirme que tout graphe planaire est le graphe d'intersection d'un ensemble de segments de droite dans le plan. Cette conjecture a été formulée par Edward R. Scheinerman dans sa thèse de doctorat de 1984, à la suite de résultats antérieurs selon lesquels chaque graphe planaire pouvait être représenté comme le graphe d'intersection d'un ensemble de courbes simples dans le plan de Ehrlich, Even et Tarjan. La conjecture a été démontrée par Jérémie Chalopin et Daniel Gonçalves en 2009.

Un exemple

Le graphe G affiché ci-dessous à gauche peut être représenté comme le graphe d'intersection de l'ensemble des segments donnés ci-dessous à droite. Ici, les sommets de G sont représentés par des segments de droite et les arêtes de G sont représentées par les points d'intersection.

     

Autres conjectures et résultats

Scheinerman a également conjecturé que des segments en seulement trois directions seraient suffisants pour représenter des graphes tricolores, et West a conjecturé que, de manière analogue, tout graphe planaire pouvait être représenté en utilisant quatre directions. Si un graphe est représenté par des segments en k directions et que deux segments ne sont pas sur une même droite, alors le graphe peut être coloré en utilisant k couleurs, une couleur pour chaque direction. Par conséquent, si chaque graphe planaire peut être représenté de cette manière avec seulement quatre directions, cela fournit une démonstration du théorème des quatre couleurs.

Hartman, Newman et Ziv et de Fraysseix, Ossona de Mendez et Pach (1991) ont montré en 1991 que tout graphe biparti planaire peut être représenté comme un graphe d'intersection de segments de droites horizontales et verticales, résultat repris par see also Czyzowicz, Kranakis et Urrutia. De Castro et al. (2002) ont prouvé que tout graphe sans triangle planaire peut être représenté comme le graphe d'intersection de segments de droites ayant seulement trois directions ; ce résultat implique le théorème de Grötzschqui dit qu'un graphe sans triangle peut être coloré en trois couleurs. de Fraysseix et Ossona de Mendez ont prouvé que si un graphe G peut être coloré en 4 couleurs de sorte qu'il n'y a pas de cycle séparateur qui utilise les quatre couleurs, alors G admet une représentation comme graphe d'intersection de segments.

Chalopin, Gonçalves et Ochem ont prouvé que les graphes planaires sont dans la classe « 1-STRING », qui est la classe des graphes d'intersection de courbes simples dans le plan qui ont au plus un point d'intersection deux-à-deux. Cette classe est intermédiaire entre la classe des graphes d'intersection de segments de la conjecture de Scheinerman et les graphes d'intersection de courbes simples de Ehrlich et al.. Il peut également être vu comme une généralisation du théorème des empilements de cercles (en) qui montre le même résultat lorsque les courbes peuvent se couper en une tangente. La preuve de la conjecture par Chalopin et Gonçalves était basée sur une amélioration de ce résultat.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Scheinerman's conjecture » (voir la liste des auteurs).

Bibliographie

• N. De Castro, F. J. Cobos, J. C. Dana et A. Márquez, « Triangle-free planar graphs as segment intersection graphs », Journal of Graph Algorithms and Applications, vol. 6, n^o 1,‎ 2002, p. 7–26 (DOI 10.7155/jgaa.00043 , MR 1898201, lire en ligne).
• J. Chalopin et D. Gonçalves, « Every planar graph is the intersection graph of segments in the plane », ACM Symposium on Theory of Computing,‎ 2009 (lire en ligne).
• J. Chalopin, D. Gonçalves et P. Ochem, « Planar graphs are in 1-STRING », Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM and SIAM,‎ 2007, p. 609–617.
• J. Czyzowicz, E. Kranakis et J. Urrutia, « A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments », Information Processing Letters, vol. 66, n^o 3,‎ 1998, p. 125–126 (DOI 10.1016/S0020-0190(98)00046-5).
• H. de Fraysseix et P. Ossona de Mendez, « Contact and intersection representations », Lecture Notes in Computer Science, Springer-Verlag, vol. 3383 « Graph Drawing, 12th International Symposium, GD 2004 »,‎ 2005, p. 217–227.
• H. de Fraysseix, P. Ossona de Mendez et J. Pach, « Representation of planar graphs by segments », Intuitive Geometry, vol. 63,‎ 1991, p. 109–117 (MR 1383616).
• G. Ehrlich, S. Even et R. E. Tarjan, « Intersection graphs of curves in the plane », Journal of Combinatorial Theory Série B, vol. 21, n^o 1,‎ 1976, p. 8–20 (DOI 10.1016/0095-8956(76)90022-8, MR 0505857).
• Herbert Grötzsch, « Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel », Wiss. Z. Martin-Luther-U. Halle-Wittenberg, math.-Nat. Reihe, vol. 8,‎ 1959, p. 109–120 (MR 0116320).
• I. B.-A. Hartman, I. Newman et R. Ziv, « On grid intersection graphs », Discrete Mathematics, vol. 87, n^o 1,‎ 1991, p. 41–52 (DOI 10.1016/0012-365X(91)90069-E, MR 1090188).
• E. R. Scheinerman, « Intersection Classes and Multiple Intersection Parameters of Graphs », Ph.D. thesis, Princeton University,‎ 1984.
• D. West, « Open problems #2 », SIAM Activity Group Newsletter in Discrete Mathematics, vol. 2, n^o 1,‎ 1991, p. 10–12.

• Daniel Gonçalves, « 3-Colorable Planar Graphs Have an Intersection Segment Representation Using 3 Slopes », Lecture Notes in Computer Science,, vol. 11789 « Graph-Theoretic Concepts in Computer Science. WG 2019 »,‎ 2019, p. 351–363 (DOI 10.1007/978-3-030-30786-8_27, HAL lirmm-02407838).