La conjetura de Scheinerman

En matemáticas , la conjetura de Scheinerman , ahora un teorema, afirma que todo grafo planar es el grafo de intersección de un conjunto de segmentos de recta en el plano. Esta conjetura fue formulada por E. R. Scheinerman en su tesis doctoral (1984) , a partir de resultados previos que indicaban que todo grafo planar podía representarse como el grafo de intersección de un conjunto de curvas simples en el plano ( Sinden 1966 ; Ehrlich, Even y Tarjan 1976 ) . Fue demostrada por Jeremie Chalopin y Daniel Gonçalves ( 2009 ) . 

Por ejemplo, el grafo G que se muestra en la figura 1 puede representarse como el grafo de intersección del conjunto de segmentos que se muestra en la figura 2. En este caso, los vértices de G están representados por segmentos de línea recta y las aristas de G están representadas por puntos de intersección.

• 
  Figura 1
• 
  Figura 2

Scheinerman también conjeturó que los segmentos con solo tres direcciones serían suficientes para representar grafos 3- coloreables , y West (1991) conjeturó que, análogamente, todo grafo planar podría representarse usando cuatro direcciones. Si un grafo se representa con segmentos que tienen solo k direcciones y no hay dos segmentos que pertenezcan a la misma línea, entonces el grafo puede colorearse usando k colores, uno para cada dirección. Por lo tanto, si todo grafo planar puede representarse de esta manera con solo cuatro direcciones, entonces se deduce el teorema de los cuatro colores . Gonçalves (2020) demostró que algunos grafos planares no pueden representarse de esa manera.

Hartman, Newman y Ziv (1991) y de Fraysseix, Ossona de Méndez y Pach (1991) demostraron que todo grafo planar bipartito puede representarse como un grafo de intersección de segmentos de línea horizontales y verticales; para este resultado véase también Czyzowicz, Kranakis y Urrutia (1998) . De Castro et al. (2002) demostraron que todo grafo planar libre de triángulos puede representarse como un grafo de intersección de segmentos de línea que tienen solo tres direcciones; este resultado implica el teorema de Grötzsch ( Grötzsch 1959 ) de que los grafos planares libres de triángulos pueden colorearse con tres colores. De Fraysseix y Ossona de Méndez (2005) demostraron que si un grafo planar G puede ser 4-coloreado de tal manera que ningún ciclo separador use los cuatro colores, entonces G tiene una representación como un grafo de intersección de segmentos.

Chalopin, Gonçalves y Ochem (2007) demostraron que los grafos planares pertenecen a 1-STRING, la clase de grafos de intersección de curvas simples en el plano que se intersecan entre sí en un máximo de un punto de cruce por par. Esta clase es intermedia entre los grafos de intersección de segmentos que aparecen en la conjetura de Scheinerman y los grafos de intersección de curvas simples sin restricciones del resultado de Ehrlich et al. También puede considerarse una generalización del teorema de empaquetamiento de círculos , que muestra el mismo resultado cuando se permite que las curvas se intersequen en una tangente. La demostración de la conjetura de Chalopin y Gonçalves (2009) se basó en una mejora de este resultado.

• De Castro, N.; Cobos, FJ; Dana, JC; Márquez, A. (2002), "Grafos planares sin triángulos como grafos de intersección de segmentos" (PDF) , Journal of Graph Algorithms and Applications , 6 (1): 7–26 , doi : 10.7155/jgaa.00043 , MR 1898201 .
• Chalopin, J.; Gonçalves, D. (2009), "Todo grafo planar es el grafo de intersección de segmentos en el plano" (PDF) , Simposio ACM sobre Teoría de la Computación.
• Chalopin, J.; Gonçalves, D.; Ochem, P. (2007), "Los grafos planares están en 1-STRING", Actas del decimoctavo simposio anual ACM-SIAM sobre algoritmos discretos , ACM y SIAM, págs. 609–617 .
• Czyzowicz, J.; Kranakis, E.; Urrutia, J. (1998), "Una prueba simple de la representación de grafos planares bipartitos como grafos de contacto de segmentos de línea recta ortogonales", Information Processing Letters , 66 (3): 125–126 , doi : 10.1016/S0020-0190(98)00046-5.
• de Fraysseix, H.; Ossona de Méndez, P. (2005), "Representaciones de contacto e intersección", en Pach, J. (ed.), Dibujo de grafos, 12.º Simposio Internacional, GD 2004 , Lecture Notes in Computer Science, vol.  3383, Springer-Verlag, pp . 217–227 .
• de Fraysseix, H.; Ossona de Méndez, P.; Pach , J. (1991), "Representación de grafos planares mediante segmentos", Geometría intuitiva , 63 : 109–117 , MR 1383616 .
• Ehrlich, G.; Even, S.; Tarjan, RE (1976), "Gráficos de intersección de curvas en el plano", Journal of Combinatorial Theory , Serie B, 21 (1): 8– 20, doi : 10.1016/0095-8956(76)90022-8 , MR 0505857 .
• Grötzsch, Herbert (1959), "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 , 8 : 109– 120, SEÑOR 0116320 .
• Hartman, IB-A.; Newman, I.; Ziv, R. (1991), "Sobre grafos de intersección de cuadrículas", Matemáticas Discretas , 87 (1): 41– 52, doi : 10.1016/0012-365X(91)90069-E , MR 1090188 .
• Scheinerman, ER (1984), Clases de intersección y parámetros de intersección múltiple de grafos , tesis doctoral, Universidad de Princeton.
• West, D. (1991), "Problemas abiertos n.° 2", SIAM Activity Group Newsletter in Discrete Mathematics , 2 ( 1): 10–12.
• Sinden, FW (1966), "Topología de circuitos de película delgada", Bell System Tech. J. , 45 : 1639– 1662.
• Gonçalves, Daniel (2020), "No todos los grafos planares están en PURE-4-DIR", Journal of Graph Algorithms and Applications , 24 (3): 293– 301, doi : 10.7155/jgaa.00533.