Ver el código de «Cajeidad»

[[File:Boxicity.svg|thumb|300px|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 [[Hiperrectángulo|cajas]] paralelas a un sistema de ejes. Es decir, debe existir una correspondencia biunívoca entre los [[Vértice (teoría de grafos)|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.{{harvtxt|Roberts|1969}} demostró que el grafo con 2''n'' vértices formado al quitar un [[emparejado perfecto]] de un [[grafo completo]] de 2''n'' 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 2''n'' 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'',<ref>E.g., véase {{harvtxt|Chandran|Francis|Sivadasan|2010}} y {{harvtxt|Chandran|Sivadasan|2007}}.</ref> aunque es más conocido como '''grafo de cóctel''' y también puede interpretarse como un [[grafo de Turán]] ''T''( 2''n'',''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,<ref>{{harvtxt|Scheinerman|1984}}.</ref> y cada [[grafo plano]] tiene cajeidad como máximo tres.<ref>{{harvtxt|Thomassen|1986}}.</ref>

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.<ref>{{harvtxt|Bellantoni|Ben-Arroyo Hartman|Przytycka|Whitesides|1993}}.</ref>

{{harvtxt|Adiga|Bhowmick|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.<ref>{{harvtxt|Chandran|Francis|Sivadasan|2010}} observó que esto se sigue del hecho de que estos grafos tienen un número polinomial de [[clique]]s. No se necesita una representación de caja explícita para enumerar todos los cliques máximos de manera eficiente.</ref> 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.<ref>Véase, por ejemplo,{{harvtxt|Agarwal|van Kreveld|Suri|1998}} y {{harvtxt|Berman|DasGupta|Muthukrishnan|Ramaswami|2001}} para aproximaciones al [[conjunto independiente]] para grafos de intersección de rectángulos, y {{harvtxt|Chlebík|Chlebíková|2005}} para obtener resultados sobre la dificultad de aproximación de estos problemas en dimensiones superiores.</ref> 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.<ref>{{harvtxt|Cozzens|1981}} muestra que calcular la cajeidad es un problema NP-completo;{{harvtxt|Yannakakis|1982}} muestra que incluso verificar si la cajeidad es como máximo 3 es de complejidad NP; finalmente {{harvtxt|Kratochvil|1994}} mostró que reconocer la cajeidad 2 es NP-difícil.</ref>

{{harvtxt|Chandran|Francis|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 [[logaritmo|logarítmico]] del [[Grado (teoría de grafos)|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 [[Complejidad parametrizada|abordable con parámetros fijos]] cuando se parametriza por el número de [[cobertura de vértices]] del grafo de entrada.<ref>{{harvtxt|Adiga|Chitnis|Saurabh|2010}}.</ref>

==Límites==
Si un grafo ''G'' tiene ''m'' aristas, entonces:

:<math>box(G)= O(\sqrt{m \cdot \log(m)})</math>.<ref>{{harvtxt|Chandran|Francis|Sivadasan|2010}}</ref><ref name="Sin_nombre-1_6Uz-1">{{harvtxt|Esperet|2016}}</ref>

Si un grafo ''G'' es ''k''-[[Degeneración (teoría de grafos)|degenerado]] (con <math>k\ge 2</math>) y tiene ''n'' vértices, entonces ''G'' tiene cajeidad <math>box(G) \le (k+2) \lceil 2e \log n \rceil</math>.<ref>{{harvtxt|Adiga|Chandran|Mathew|2014}}</ref>

Si un grafo ''G'' no tiene el grafo completo en los ''t'' vértices como [[Menor (teoría de grafos)|menor]], entonces <math>box(G)= O(t^2 \log t)</math><ref>{{harvtxt|Esperet|Wiechert|2018}}</ref> mientras haya grafos sin grafo completo en los ''t'' vértices como [[Menor (teoría de grafos)|menor]], y con cajeidad <math>\Omega(t \sqrt{\log t})</math>.<ref name="Sin_nombre-1_6Uz-1"/> En particular, cualquier grafo ''G'' tiene la cajeidad <math>box(G)= O(\mu(G)^2 \log \mu(G))</math>, donde <math>\mu(G)</math> denota el [[invariante de grafo de Colin de Verdière|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. <!--For a graph G, its cubicity cub(G) is the minimum dimension k such that G is representable as the intersection graph of (axis-parallel) cubes in k-dimensional space.--> Boxicity es una generalización de cubicity.
* La [[Esfericidad (teoría de grafos)|esfericidad]] se define de la misma forma que la cajeidad pero con esferas de diámetro unitario. <!-- The sphericity of a graph G is the smallest n such that the vertices in G can be mapped into unit-diameter spheres in n-space in such a way that two vertices are adjacent in G if and only if their assigned spheres intersect.-->

==Referencias==
{{listaref|2}}

==Bibliografía==
{{refbegin|2}}
*{{citation
|first1= Abhijin|last1= Adiga 
|first2= Diptendu|last2= Bhowmick
|last3= Chandran|first3= L. Sunil
|title= Boxicity and Poset Dimension
|journal= SIAM Journal on Discrete Mathematics
|volume= 25|year= 2011|pages= 1687–1698|doi= 10.1137/100786290
|issue= 4|arxiv= 1003.2357}}.
*{{citation
|first1= Abhijin|last1= Adiga 
|last2= Chandran|first2= L. Sunil
|first3= Rogers|last3= Mathew
|title= Cubicity, Degeneracy, and Crossing Number
|journal= European Journal of Combinatorics
|volume= 35|year= 2014|pages= 2–12|doi= 10.1016/j.ejc.2013.06.021
|arxiv= 1105.5225}}.
*{{citation
|last1= Adiga
|first1= Abhijin
|last2= Chitnis
|first2= Rajesh
|last3= Saurabh
|first3= Saket
|contribution= Parameterized algorithms for boxicity
|doi= 10.1007/978-3-642-17517-6_33
|pages= 366–377
|series= Lecture Notes in Computer Science
|title= Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I
|url= http://www.wisdom.weizmann.ac.il/~chitnis/fptBoxicity.pdf
|volume= 6506
|year= 2010
|access-date= 2018-01-22
|archive-url= https://web.archive.org/web/20170830050212/http://www.wisdom.weizmann.ac.il/~chitnis/fptBoxicity.pdf
|archive-date= 2017-08-30
 }}
*{{citation
|first1= Pankaj K.|last1= Agarwal|author1-link= Pankaj K. Agarwal
|first2= Marc|last2= van Kreveld
|first3= Subhash|last3= Suri|author3-link= Subhash Suri
|title= Label placement by maximum independent set in rectangles
|journal= [[ Computational Geometry (journal)|Computational Geometry Theory and Applications]]
|volume= 11|year= 1998|pages= 209–218|doi= 10.1016/S0925-7721(98)00028-5
|issue= 3–4|hdl= 1874/18908|hdl-access= free }}.
*{{citation
|last1= Bellantoni|first1= Stephen J.
|last2= Ben-Arroyo Hartman|first2= Irith
|last3= Przytycka|first3= Teresa|author3-link= Teresa Przytycka
|last4=  Whitesides|first4= Sue|author4-link= Sue Whitesides
|title= Grid intersection graphs and boxicity
|journal= [[ Discrete Mathematics (journal)|Discrete Mathematics]]
|volume= 114|issue= 1–3|pages= 41–49|year= 1993|doi= 10.1016/0012-365X(93)90354-V }}.
*{{citation
|first1= Piotr|last1= Berman
|first2= B.|last2= DasGupta
|first3= S.|last3= Muthukrishnan|author3-link= S. Muthukrishnan (computer scientist)
|first4= S.|last4= Ramaswami
|title= Efficient approximation algorithms for tiling and packing problems with rectangles
|journal= J. Algorithms
|volume= 41|year= 2001|pages= 443–470|doi= 10.1006/jagm.2001.1188
|issue= 2}}.
*{{citation
|last1= Chandran|first1= L. Sunil
|last2= Francis|first2= Mathew C.
|last3= Sivadasan|first3= Naveen
|arxiv= cs.DM/0605013
|doi= 10.1007/s00453-008-9163-5
|issue= 2
|journal= Algorithmica
|mr= 2576537
|pages= 129–140
|title= Geometric representation of graphs in low dimension using axis parallel boxes
|volume= 56
|year= 2010|s2cid= 17838951
 }}.
*{{citation
|last1= Chandran|first1= L. Sunil
|last2= Sivadasan|first2= Naveen
|title= Boxicity and treewidth
|journal= [[ Journal of Combinatorial Theory]]|series= [[ Series B]]
|volume= 97|issue= 5|year= 2007|pages= 733–744|doi= 10.1016/j.jctb.2006.12.004
|arxiv= math.CO/0505544|s2cid= 9854207
 }}.
*{{citation
|first1= Miroslav|last1= Chlebík
|first2= Janka|last2= Chlebíková|author2-link= Janka Chlebíková
|contribution= Approximation hardness of optimization problems in intersection graphs of ''d''-dimensional boxes
|title= Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
|year= 2005|pages= 267–276|url= http://portal.acm.org/citation.cfm?id=1070470}}.
*{{citation
|first= M. B.|last= Cozzens
|title= Higher and Multidimensional Analogues of Interval Graphs
|publisher= Rutgers University
|series= Ph.D. thesis
|year= 1981}}.
*{{citation
|first= Louis|last= Esperet 
|title= Boxicity and topological invariants
|journal= European Journal of Combinatorics
|volume= 51|year= 2016|pages= 495–499|doi= 10.1016/j.ejc.2015.07.020|arxiv= 1503.05765|s2cid= 5548385 
 }}.
*{{citation
|first1= Louis|last1= Esperet
|first2= Veit|last2= Wiechert
|title= Boxicity, poset dimension, and excluded minors
|journal= Electronic Journal of Combinatorics
|volume= 25|issue= 4|year= 2018|pages= #P4.51|doi= 10.37236/7787
|url= http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p51|arxiv= 1804.00850|s2cid= 119148637
}}.
*{{citation
|first= Jan|last= Kratochvil|authorlink= Jan Kratochvíl
|title= A special planar satisfiability problem and a consequence of its NP–completeness
|journal= Discrete Applied Mathematics
|volume= 52|year= 1994|pages= 233–252|doi= 10.1016/0166-218X(94)90143-0
|issue= 3}}.
*{{citation
|last1= Quest|first1= M.
|last2= Wegner|first2= G.
|title= Characterization of the graphs with boxicity ≤ 2
|journal= Discrete Mathematics
|volume= 81|issue= 2|year= 1990|pages= 187–192|doi= 10.1016/0012-365X(90)90151-7 }}.
*{{citation
|last= Roberts|first= F. S.|authorlink= Fred S. Roberts
|contribution= On the boxicity and cubicity of a graph
|title= Recent Progress in Combinatorics
|editor-first= W. T.|editor-last= Tutte|editor-link= W. T. Tutte
|publisher= Academic Press|isbn= 978-0-12-705150-5
|year= 1969|pages= 301–310}}.
*{{citation
|first= E. R.|last= Scheinerman|authorlink= Ed Scheinerman
|title= Intersection Classes and Multiple Intersection Parameters
|series= Ph. D thesis
|publisher= Princeton University
|year= 1984}}.
*{{citation
|first= Carsten|last= Thomassen|authorlink= Carsten Thomassen
|title= Interval representations of planar graphs
|journal= Journal of Combinatorial Theory, Series B
|volume= 40|year= 1986|pages= 9–20|doi= 10.1016/0095-8956(86)90061-4 }}.
*{{citation
|first= Mihalis|last= Yannakakis 
|authorlink= Mihalis Yannakakis
|title= The complexity of the partial order dimension problem
|journal= SIAM Journal on Algebraic and Discrete Methods
|volume= 3|year= 1982|pages= 351–358|doi= 10.1137/0603036
|issue= 3}}.
{{refend}}

{{Control de autoridades}}
[[Categoría:Teoría de grafos geométricos]]
[[Categoría:Invariantes de grafos]]