Cajeidad

Un grafo de intersección de rectángulos, con cajeidad dos

En teoría de grafos, la cajeidad (boxicity en inglés) es un invariante de grafo, introducido por Fred S. Roberts en 1969.

La cajeidad de un grafo es la dimensión mínima en la que un grafo dado puede representarse como un grafo de intersección de cajas paralelas a un sistema de ejes. Es decir, debe existir una correspondencia biunívoca entre los vértices del grafo y un conjunto de cajas, tal que dos cajas se intersecan si y solo si hay una arista en el grafo que conecta los vértices correspondientes.

Ejemplos

La figura muestra un grafo con seis vértices y su representación como un grafo de intersección de rectángulos (cajas bidimensionales). Este grafo no se puede representar como un grafo de intersección de cajas en ninguna dimensión inferior, por lo que su cajeidad es dos.Roberts (1969) demostró que el grafo con 2n vértices formado al quitar un emparejado perfecto de un grafo completo de 2n vértices tiene cajeidad exactamente n: cada par de vértices desconectados debe estar representado por cajas que están separadas en una dimensión diferente que cada otro par. Se puede encontrar una representación de caja de este grafo con dimensión exactamente n al engrosar cada una de las 2n facetas de un hipercubo de dimensión n en una caja. Debido a estos resultados, a este grafo se le ha denominado grafo de Roberts,​ aunque es más conocido como grafo de cóctel y también puede interpretarse como un grafo de Turán T( 2n,n).

Relación con otras clases de grafos

Un grafo tiene cajeidad como máximo uno si y solo si es un grafo de intervalos; la cajeidad de un grafo arbitrario G es el número mínimo de grafos de intervalo en el mismo conjunto de vértices de manera que la intersección de los conjuntos de aristas de los grafos de intervalo es G. Cada grafo plano exterior tiene cajeidad como máximo dos,​ y cada grafo plano tiene cajeidad como máximo tres.​

Si un grafo bipartito tiene cajeidad dos, se puede representar como un grafo de intersección de segmentos de línea recta paralelos al eje en el plano.​

Adiga, Bhowmick y Chandran (2011) probó que la cajeidad de un grafo bipartito G está dentro de un factor 2 de la dimensión de orden del conjunto parcialmente ordenado de altura-dos asociado a G de la siguiente manera: el conjunto de elementos mínimos corresponde a un conjunto partito de G, el conjunto de elementos máximos corresponde al segundo conjunto parcial de G, y dos elementos son comparables si los vértices correspondientes son adyacentes en G. De manera equivalente, la dimensión de orden de un conjunto parcialmente ordenado P de altura dos está dentro de un factor 2 de la cajeidad del grafo de comparabilidad de P (que es bipartito, ya que P tiene altura dos).

Resultados algorítmicos

Muchos problemas de grafos se pueden resolver o aproximar de manera más eficiente para grafos con cajeidad acotada que para otros grafos; por ejemplo, el problema del clique se puede resolver en tiempo polinomial para grafos con cajeidad acotada.​ Para algunos otros problemas de grafos, se puede encontrar una solución o aproximación eficiente si se conoce una representación de caja de baja dimensión.​ Sin embargo, encontrar tal representación puede ser difícil: es NP-completo probar si la cajeidad de un grafo dado es como mucho un valor dado K, incluso para K = 2.​

Chandran, Francis y Sivadasan (2010) describió algoritmos para encontrar representaciones de grafos arbitrarios como grafos de intersección de cajas, con una dimensión dentro de un factor logarítmico del grado máximo del grafo; este resultado proporciona un límite superior de la cajeidad del grafo.

A pesar de ser difícil por su parámetro natural, la cajeidad es abordable con parámetros fijos cuando se parametriza por el número de cobertura de vértices del grafo de entrada.​

Límites

Si un grafo G tiene m aristas, entonces:

$box(G)=O({\sqrt {m\cdot \log(m)}})$.​​

Si un grafo G es k-degenerado (con $k\geq 2$) y tiene n vértices, entonces G tiene cajeidad $box(G)\leq (k+2)\lceil 2e\log n\rceil$.​

Si un grafo G no tiene el grafo completo en los t vértices como menor, entonces $box(G)=O(t^{2}\log t)$​ mientras haya grafos sin grafo completo en los t vértices como menor, y con cajeidad $\Omega (t{\sqrt {\log t}})$.​ En particular, cualquier grafo G tiene la cajeidad $box(G)=O(\mu (G)^{2}\log \mu (G))$, donde $\mu (G)$ denota el invariante de Colin de Verdière de G.

Invariantes de grafos relacionados

• La cubicidad se define de la misma manera que la cajeidad pero con hipercubo paralelos al eje en lugar de hiperrectángulos. Boxicity es una generalización de cubicity.
• La esfericidad se define de la misma forma que la cajeidad pero con esferas de diámetro unitario.

Bibliografía

• Adiga, Abhijin; Bhowmick, Diptendu; Chandran, L. Sunil (2011), «Boxicity and Poset Dimension», SIAM Journal on Discrete Mathematics 25 (4): 1687-1698, arXiv:1003.2357, doi:10.1137/100786290 ..
• Adiga, Abhijin; Chandran, L. Sunil; Mathew, Rogers (2014), «Cubicity, Degeneracy, and Crossing Number», European Journal of Combinatorics 35: 2-12, arXiv:1105.5225, doi:10.1016/j.ejc.2013.06.021 ..
• Adiga, Abhijin; Chitnis, Rajesh; Saurabh, Saket (2010), «Parameterized algorithms for boxicity», Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, Lecture Notes in Computer Science 6506, pp. 366-377, doi:10.1007/978-3-642-17517-6_33, archivado desde el original el 30 de agosto de 2017, consultado el 22 de enero de 2018 .
• Agarwal, Pankaj K.; van Kreveld, Marc; Suri, Subhash (1998), «Label placement by maximum independent set in rectangles», Computational Geometry Theory and Applications 11 (3–4): 209-218, doi:10.1016/S0925-7721(98)00028-5, hdl:1874/18908 ..
• Bellantoni, Stephen J.; Ben-Arroyo Hartman, Irith; Przytycka, Teresa; Whitesides, Sue (1993), «Grid intersection graphs and boxicity», Discrete Mathematics 114 (1–3): 41-49, doi:10.1016/0012-365X(93)90354-V ..
• Berman, Piotr; DasGupta, B.; Muthukrishnan, S.; Ramaswami, S. (2001), «Efficient approximation algorithms for tiling and packing problems with rectangles», J. Algorithms 41 (2): 443-470, doi:10.1006/jagm.2001.1188 ..
• Chandran, L. Sunil; Francis, Mathew C.; Sivadasan, Naveen (2010), «Geometric representation of graphs in low dimension using axis parallel boxes», Algorithmica 56 (2): 129-140, MR 2576537, S2CID 17838951, arXiv:cs.DM/0605013, doi:10.1007/s00453-008-9163-5 ..
• Chandran, L. Sunil; Sivadasan, Naveen (2007), «Boxicity and treewidth», Journal of Combinatorial Theory, Series B 97 (5): 733-744, S2CID 9854207, arXiv:math.CO/0505544, doi:10.1016/j.jctb.2006.12.004 ..
• Chlebík, Miroslav; Chlebíková, Janka (2005), «Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes», Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 267-276 ..
• Cozzens, M. B. (1981), Higher and Multidimensional Analogues of Interval Graphs, Ph.D. thesis, Rutgers University ..
• Esperet, Louis (2016), «Boxicity and topological invariants», European Journal of Combinatorics 51: 495-499, S2CID 5548385, arXiv:1503.05765, doi:10.1016/j.ejc.2015.07.020 ..
• Esperet, Louis; Wiechert, Veit (2018), «Boxicity, poset dimension, and excluded minors», Electronic Journal of Combinatorics 25 (4): #P4.51, S2CID 119148637, arXiv:1804.00850, doi:10.37236/7787 ..
• Kratochvil, Jan (1994), «A special planar satisfiability problem and a consequence of its NP–completeness», Discrete Applied Mathematics 52 (3): 233-252, doi:10.1016/0166-218X(94)90143-0 ..
• Quest, M.; Wegner, G. (1990), «Characterization of the graphs with boxicity ≤ 2», Discrete Mathematics 81 (2): 187-192, doi:10.1016/0012-365X(90)90151-7 ..
• Roberts, F. S. (1969), «On the boxicity and cubicity of a graph», en Tutte, W. T., ed., Recent Progress in Combinatorics, Academic Press, pp. 301-310, ISBN 978-0-12-705150-5 ..
• Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters, Ph. D thesis, Princeton University ..
• Thomassen, Carsten (1986), «Interval representations of planar graphs», Journal of Combinatorial Theory, Series B 40: 9-20, doi:10.1016/0095-8956(86)90061-4 ..
• Yannakakis, Mihalis (1982), «The complexity of the partial order dimension problem», SIAM Journal on Algebraic and Discrete Methods 3 (3): 351-358, doi:10.1137/0603036 ..

• Datos: Q4951712