En teoría de grafos , el grosor de un grafo G es el número mínimo de grafos planos en los que se pueden dividir los bordes de G. Es decir, si existe una colección de k grafos planos, todos con el mismo conjunto de vértices, de modo que la unión de estos grafos planos es G , entonces el grosor de G es como máximo k . [1] [2] En otras palabras, el espesor de un gráfico que es el número mínimo de planas subgraphs cuya unión es igual para representar gráficamente G . [3]
Por lo tanto, una gráfica plana tiene espesor 1. Las gráficas de espesor 2 se denominan gráficas biplanares . El concepto de grosor se origina en la conjetura de Frank Harary de 1962 : para cualquier gráfico de 9 puntos, ya sea él mismo o su gráfico complementario no es plano . El problema equivale a determinar si la gráfica completa K 9 es biplanar (no lo es, y la conjetura es cierta). [4] Petra Mutzel , Thomas Odenthal y Mark Scharbrodt redactaron una encuesta exhaustiva [3] sobre el estado del arte del tema a partir de 1998 . [5]
Gráficos específicos
El grosor de la gráfica completa en n vértices, K n , es
excepto cuando n = 9, 10 para el cual el espesor es tres. [6] [7]
Con algunas excepciones, el grosor de un gráfico bipartito completo K a, b es generalmente: [8] [9]
Problemas relacionados
Cada bosque es plano y cada gráfico plano se puede dividir en un máximo de tres bosques. Por lo tanto, el grosor de cualquier gráfico G es como máximo igual a la arboricidad del mismo gráfico (el número mínimo de bosques en los que se puede dividir) y al menos igual a la arboricidad dividida por tres. [2] [10] El grosor de G también está dentro de los factores constantes de otro invariante gráfico estándar , la degeneración , definida como el máximo, sobre los subgrafos de G , del grado mínimo dentro del subgrafo. Si un gráfico de n- vértice tiene un grosor t, entonces necesariamente tiene como máximo t (3 n - 6) bordes, de lo cual se sigue que su degeneración es como máximo 6 t - 1 . En la otra dirección, si un gráfico tiene degeneración D entonces tiene arboricity, y espesor, como máximo D .
El grosor está estrechamente relacionado con el problema de la incrustación simultánea . [11] Si dos o más gráficos planos comparten el mismo conjunto de vértices, entonces es posible incrustar todos estos gráficos en el plano, con los bordes dibujados como curvas, de modo que cada vértice tenga la misma posición en todos los dibujos diferentes. Sin embargo, puede que no sea posible construir un dibujo de este tipo manteniendo los bordes dibujados como segmentos de línea recta .
Un invariante de gráfico diferente, el espesor rectilíneo o el espesor geométrico de un gráfico G , cuenta el número más pequeño de gráficos planos en los que se puede descomponer G sujeto a la restricción de que todos estos gráficos se pueden dibujar simultáneamente con bordes rectos. El grosor del libro agrega una restricción adicional, que todos los vértices se dibujen en posición convexa , formando un diseño circular del gráfico. Sin embargo, en contraste con la situación de arboricidad y degeneración, no hay dos de estos tres parámetros de espesor siempre dentro de un factor constante el uno del otro. [12]
Complejidad computacional
Es NP-difícil calcular el grosor de un gráfico dado y NP-completo para probar si el grosor es como máximo dos. [13] Sin embargo, la conexión con la arboricidad permite aproximar el espesor dentro de una relación de aproximación de 3 en tiempo polinomial .
Referencias
- ^ Tutte, WT (1963), "El grosor de un gráfico", Indag. Matemáticas. , 25 : 567–577, MR 0157372.
- ^ a b Mutzel, Petra ; Odenthal, Thomas; Scharbrodt, Mark (1998), "El grosor de los gráficos: una encuesta", Gráficos y combinatoria , 14 (1): 59–73, doi : 10.1007 / PL00007219 , MR 1617664.
- ^ a b Christian A. Duncan, Sobre el grosor del gráfico, el grosor geométrico y los teoremas del separador , CCCG 2009, Vancouver, BC, 17-19 de agosto de 2009
- ^ Mäkinen, Erkki; Poranen, Timo (2012). "Una bibliografía comentada sobre el grosor, el grosor y la arboricidad de un gráfico" . Missouri J. Math. Sci . 24 (1): 76–87.
- ^ Petra Mutzel , Thomas Odenthal y Mark Scharbrodt, El grosor de los gráficos: una encuesta
- ^ Mutzel, Odenthal y Scharbrodt (1998) , Teorema 3.2.
- ^ Alekseev, VB; Gončakov, VS (1976), "El grosor de un gráfico completo arbitrario", Mat. Sb. , Serie nueva, 101 (143): 212–230, MR 0460162.
- ^ Mutzel, Odenthal y Scharbrodt (1998) , Teorema 3.4.
- ^ Beineke, Lowell W .; Harary, Frank ; Moon, John W. (1964), "Sobre el grosor del gráfico bipartito completo", Proc. Cambridge Philos. Soc. , 60 : 1–5, doi : 10.1017 / s0305004100037385 , MR 0158388.
- ^ Dean, Alice M .; Hutchinson, Joan P .; Scheinerman, Edward R. (1991), "Sobre el grosor y la arboricidad de un gráfico", Journal of Combinatorial Theory , Serie B, 52 (1): 147-151, doi : 10.1016 / 0095-8956 (91) 90100-X , MR 1109429.
- ^ Latón, Peter; Cenek, Eowyn; Duncan, Cristian A .; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P .; Kobourov, Stephen G .; Lubiw, Anna ; Mitchell, Joseph SB (2007), "Sobre incrustaciones de gráficos planos simultáneos", Geometría computacional , 36 (2): 117–130, doi : 10.1016 / j.comgeo.2006.05.006 , MR 2278011.
- ^ Eppstein, David (2004), "Separando espesor de espesor geométrico", Hacia una teoría de grafos geométricos , Contemp. Math., 342 , Amer. Matemáticas. Soc., Providence, RI, págs. 75–86, arXiv : math / 0204252 , doi : 10.1090 / conm / 342/06132 , MR 2065254.
- ^ Mansfield, Anthony (1983), "Determinar el grosor de los gráficos es NP-hard", Actas matemáticas de la Sociedad Filosófica de Cambridge , 93 (1): 9-23, doi : 10.1017 / S030500410006028X , MR 0684270.