En matemáticas , la conjetura de Scheinerman , ahora un teorema, establece que cada gráfico plano es el gráfico de intersección de un conjunto de segmentos de línea en el plano. Esta conjetura fue formulada por ER Scheinerman en su Ph.D. tesis (1984) , siguiendo los resultados anteriores de que cada gráfico plano podría representarse como el gráfico de intersección de un conjunto de curvas simples en el plano ( Ehrlich, Even y Tarjan 1976 ). Fue probado por Jeremie Chalopin y Daniel Gonçalves ( 2009 ).
Por ejemplo, el gráfico G que se muestra a continuación a la izquierda puede representarse como el gráfico de intersección del conjunto de segmentos que se muestra a continuación a la derecha. Aquí, los vértices de G están representados por segmentos de línea recta y los bordes de G están representados por puntos de intersección.
Scheinerman también conjeturó que los segmentos con sólo tres direcciones serían suficientes para representar gráficas de 3 colores , y West (1991) conjeturó que, de manera análoga, todas las gráficas planas podrían representarse usando cuatro direcciones. Si un gráfico se representa con segmentos que tienen solo k direcciones y no hay dos segmentos que pertenezcan a la misma línea, entonces el gráfico se puede colorear usando k colores, un color para cada dirección. Por lo tanto, si cada gráfico plano se puede representar de esta manera con solo cuatro direcciones, se sigue el teorema de los cuatro colores .
Hartman, Newman y Ziv (1991) y de Fraysseix, Ossona de Méndez y Pach (1991) demostraron que todo gráfico plano bipartito se puede representar como un gráfico de intersección de segmentos de línea horizontal y vertical; para este resultado ver también Czyzowicz, Kranakis & Urrutia (1998) . De Castro y col. (2002) demostraron que todo gráfico plano sin triángulos se puede representar como un gráfico de intersección de segmentos de línea que tienen sólo tres direcciones; este resultado implica el teorema de Grötzsch ( Grötzsch 1959 ) de que los gráficos planos sin triángulos se pueden colorear con tres colores. de Fraysseix y Ossona de Méndez (2005) demostraron que si un gráfico plano G puede tener 4 colores de tal manera que ningún ciclo de separación utilice los cuatro colores, entonces G tiene una representación como un gráfico de intersección de segmentos.
Chalopin, Gonçalves & Ochem (2007) demostraron que las gráficas planas están en 1-STRING, la clase de gráficas de intersección de curvas simples en el plano que se cruzan entre sí en como máximo un punto de cruce por par. Esta clase es intermedia entre los gráficos de intersección de segmentos que aparecen en la conjetura de Scheinerman y los gráficos de intersección de curvas simples sin restricciones del resultado de Ehrlich et al. También se puede ver como una generalización del teorema del empaquetamiento de círculos , que muestra el mismo resultado cuando se permite que las curvas se crucen en una tangente. La prueba de la conjetura de Chalopin & Gonçalves (2009) se basó en una mejora de este resultado.
Referencias
- De Castro, N .; Cobos, FJ; Dana, JC; Márquez, A. (2002), "Gráficos planos sin triángulos como gráficos 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), "Cada gráfico plano es el gráfico 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), "Las gráficas planas 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 gráficos planos bipartitos como los gráficos 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 Mendez, P. (2005), "Representaciones de contacto e intersección", en Pach, J. (ed.), Graph Drawing, 12th International Symposium, GD 2004 , Lecture Notes in Computer Science, 3383 , Springer-Verlag, págs. . 217–227.
- de Fraysseix, H .; Ossona de Méndez, P .; Pach, J. (1991), "Representación de gráficos planos por segmentos", Geometría intuitiva , 63 : 109-117, MR 1383616.
- Ehrlich, G .; Incluso, 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, MR 0116320.
- Hartman, IB-A .; Newman, I .; Ziv, R. (1991), "On grid intersection graphs", Discrete Mathematics , 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 gráficos , Ph.D. tesis, Universidad de Princeton.
- West, D. (1991), "Problemas abiertos # 2", Boletín del Grupo de Actividades SIAM en Matemáticas Discretas , 2 (1): 10–12.