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 al eje. 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 que conecta los vértices correspondientes.

Ejemplos

La figura muestra un grafo con seis vértices y una representación de este grafo 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 boxicidad es dos.

Roberts (1969) mostró que el grafo con 2n vértices formado al quitar un perfect matching de un grafo completo en 2n vértices tiene boxicidad exactamente n: cada par de vértices desconectados debe estar representado por cajas que son separados 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 entenderse como Grafo de Turán T( 2n,n).

Relación con otras clases de grafos

Un grafo tiene boxicidad como máximo uno si y solo si es un grafo de intervalos; la boxicidad 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 boxicidad como máximo dos,​ y cada grafo plano tiene boxicidad como máximo tres.​

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

Adiga, Bhowmick y Chandran (2011) probó que la boxicidad de un grafo bipartito G está dentro de un factor 2 del order dimension de la altura-dos conjunto parcialmente ordenado 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, el order dimension de un conjunto parcialmente ordenado P de altura dos está dentro de un factor 2 de la boxicidad del comparability graph 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 boxicidad acotada que para otros grafos; por ejemplo, el problema del clique se puede resolver en tiempo polinomial para grafos con boxicidad 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 boxicidad de un grafo dado es como mucho un valor dado K, incluso para K = 2.​ Chandran, Francis y Sivadasan (2010) describe algoritmos para encontrar representaciones de grafos arbitrarios como grafos de intersección de cajas, con una dimensión que está dentro de un factor logaritmoic del maximum degree del grafo; este resultado proporciona un límite superior en la boxicidad del grafo.

A pesar de ser difícil por su parámetro natural, la boxicidad es fixed-parameter tractable cuando se parametriza por el número cobertura de vértices del grafo de entrada.​

Límites

Si un grafo G tiene aristas m, entonces: $box(G)=O({\sqrt {m\cdot \log(m)}})$.​​

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

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

Invariantes de grafos relacionados

• La cubicidad se define de la misma manera que la boxicidad 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