Cajeidad

En teoría de grafos, la cajeidad (boxicity en inglés) es un invariante de grafo, introducido por Fred S. Roberts en 1969.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.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.Debido a estos resultados, a este grafo se le ha denominado grafo de Roberts,[1]​ aunque es más conocido como grafo de cóctel y también puede interpretarse como un grafo de Turán T( 2n,n).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.[6]​ 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.[7]​ 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.) y tiene n vértices, entonces G tiene cajeidad[10]​ En particular, cualquier grafo G tiene la cajeidad