Espesor (teoría de grafos)

De Wikipedia, la enciclopedia libre

En teoría de grafos, el espesor (o también grosor) de un grafo G es el número mínimo de grafos planos en el que se pueden dividir las aristas de G. Es decir, si existe una colección de grafos planos k, todos con el mismo conjunto de vértices, tal 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 grafo es el número mínimo de planos subgrafos cuya unión es igual al grafo G.[3]​

Así, un grafo plano tiene espesor 1. Los grafos de espesor 2 se denominan grafos biplanares. El concepto de espesor se origina en la conjetura planteada por Frank Harary en 1962: cualquier grafo de 9 puntos, ya sea él mismo o su grafo complemento, es no-plano. El problema es equivalente a determinar si el grafo completo K9 es biplanar (no lo es, y la conjetura es verdadera).[4]​[3]​ Petra Mutzel, Thomas Odenthal y Mark Scharbrodt escribieron una recopilación exhaustiva sobre el estado del arte del tema en 1998.[5]​

Grafos específicos[editar]

El grosor de un grafo completo sobre n vértices, Kn, es

excepto cuando n = 9, 10, casos para los que el espesor es tres.[6]​[7]​

Con algunas excepciones, el grosor de un grafo bipartito completo Ka,b es generalmente:[8]​[9]​

Problemas relacionados[editar]

Cada bosque es plano, y cada grafo plano se puede dividir en tres bosques como máximo. Por lo tanto, el grosor de cualquier grafo G es como máximo igual a la arboricidad del mismo grafo (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 de grafos estándar, su degeneración, definido como el máximo, sobre los subgrafos de G, del grado mínimo dentro del subgrafo. Si un grafo de n vértices tiene un grosor t, entonces necesariamente tiene como máximo t(3n − 6) aristas, de lo que se deduce que su degeneración es como máximo 6t − 1. En la otra dirección, si un grafo tiene degeneración D, entonces tiene arboricidad y espesor como máximo D.

El espesor está estrechamente relacionado con el problema de embebido simultáneo.[11]​ Si dos o más grafos planos comparten el mismo conjunto de vértices, entonces es posible incrustar todos estos grafos en el plano, con las aristas dibujadas 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 las aristas dibujadas como segmentos rectos.

Un invariante de grafo diferente, el grosor rectilíneo o el grosor geométrico de un grafo G, cuenta el número más pequeño de grafos planos en los que se puede descomponer G sujeto a la restricción de que todos estos grafos se pueden dibujar simultáneamente con aristas rectas. El espesor del libro agrega una restricción adicional, de forma que todos los vértices se dibujen en posición convexa, formando una disposición circular del grafo. Sin embargo, en contraste con la situación de arboricidad y degeneración, ninguno de estos tres parámetros de espesor se presenta siempre guardando un factor constante entre unos y otros.[12]​

Complejidad computacional[editar]

El cálculo del grosor de un grafo dado es un problema de dificultad NP, mientras que comprobar si el grosor es como máximo dos es un problema NP-completo.[13]​ Sin embargo, la conexión con la arboricidad permite aproximar el grosor dentro de un algoritmo de aproximación de razón 3 en tiempo polinómico.

Referencias[editar]

  1. ↑ Tutte, W. T. (1963), «The thickness of a graph», Indag. Math. 25: 567-577, MR 0157372 ..
  2. ↑ a b Mutzel, Petra; Odenthal, Thomas; Scharbrodt, Mark (1998), «The thickness of graphs: a survey», Graphs and Combinatorics 14 (1): 59-73, MR 1617664, doi:10.1007/PL00007219 ..
  3. ↑ a b Christian A. Duncan, On Graph Thickness, Geometric Thickness, and Separator Theorems, CCCG 2009, Vancouver, BC, August 17–19, 2009
  4. ↑ Mäkinen, Erkki; Poranen, Timo (2012). «An Annotated Bibliography on the Thickness, Outerthickness, and Arboricity of a Graph». Missouri J. Math. Sci. 24 (1): 76-87. 
  5. ↑ Petra Mutzel, Thomas Odenthal and Mark Scharbrodt, The Thickness of Graphs: A Survey
  6. ↑ Mutzel, Odenthal y Scharbrodt (1998), Theorem 3.2.
  7. ↑ Alekseev, V. B.; Gončakov, V. S. (1976), «The thickness of an arbitrary complete graph», Mat. Sb., New Series 101 (143): 212-230, MR 0460162 ..
  8. ↑ Mutzel, Odenthal y Scharbrodt (1998), Theorem 3.4.
  9. ↑ Beineke, Lowell W.; Harary, Frank; Moon, John W. (1964), «On the thickness of the complete bipartite graph», Proc. Cambridge Philos. Soc. 60: 1-5, MR 0158388, doi:10.1017/s0305004100037385 ..
  10. ↑ Dean, Alice M.; Hutchinson, Joan P.; Scheinerman, Edward R. (1991), «On the thickness and arboricity of a graph», Journal of Combinatorial Theory, Series B 52 (1): 147-151, MR 1109429, doi:10.1016/0095-8956(91)90100-X ..
  11. ↑ Brass, Peter; Cenek, Eowyn; Duncan, Cristian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna et al. (2007), «On simultaneous planar graph embeddings», Computational Geometry 36 (2): 117-130, MR 2278011, doi:10.1016/j.comgeo.2006.05.006  ..
  12. ↑ Eppstein, David (2004), «Separating thickness from geometric thickness», Towards a theory of geometric graphs, Contemp. Math. 342, Amer. Math. Soc., Providence, RI, pp. 75-86, MR 2065254, arXiv:math/0204252, doi:10.1090/conm/342/06132 ..
  13. ↑ Mansfield, Anthony (1983), «Determining the thickness of graphs is NP-hard», Mathematical Proceedings of the Cambridge Philosophical Society 93 (1): 9-23, MR 684270, doi:10.1017/S030500410006028X ..
Obtenido de «https://es.wikipedia.org/w/index.php?title=Espesor_(teoría_de_grafos)&oldid=145844853»