Ir al contenido

Cajeidad

De Wikipedia, la enciclopedia libre
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

[editar]

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,[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).

Relación con otras clases de grafos

[editar]

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,[2]​ y cada grafo plano tiene cajeidad como máximo tres.[3]

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.[4]

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

[editar]

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.[5]​ 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.[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.

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.[8]

Límites

[editar]

Si un grafo G tiene m aristas, entonces:

.[9][10]

Si un grafo G es k-degenerado (con ) y tiene n vértices, entonces G tiene cajeidad .[11]

Si un grafo G no tiene el grafo completo en los t vértices como menor, entonces [12]​ mientras haya grafos sin grafo completo en los t vértices como menor, y con cajeidad .[10]​ En particular, cualquier grafo G tiene la cajeidad , donde denota el invariante de Colin de Verdière de G.

Invariantes de grafos relacionados

[editar]
  • 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.

Referencias

[editar]
  1. E.g., véase Chandran, Francis y Sivadasan (2010) y Chandran y Sivadasan (2007).
  2. Scheinerman (1984).
  3. Thomassen (1986).
  4. Bellantoni et al. (1993).
  5. Chandran, Francis y Sivadasan (2010) observó que esto se sigue del hecho de que estos grafos tienen un número polinomial de cliques. No se necesita una representación de caja explícita para enumerar todos los cliques máximos de manera eficiente.
  6. Véase, por ejemplo,Agarwal, van Kreveld y Suri (1998) y Berman et al. (2001) para aproximaciones al conjunto independiente para grafos de intersección de rectángulos, y Chlebík y Chlebíková (2005) para obtener resultados sobre la dificultad de aproximación de estos problemas en dimensiones superiores.
  7. Cozzens (1981) muestra que calcular la cajeidad es un problema NP-completo;Yannakakis (1982) muestra que incluso verificar si la cajeidad es como máximo 3 es de complejidad NP; finalmente Kratochvil (1994) mostró que reconocer la cajeidad 2 es NP-difícil.
  8. Adiga, Chitnis y Saurabh (2010).
  9. Chandran, Francis y Sivadasan (2010)
  10. a b Esperet (2016)
  11. Adiga, Chandran y Mathew (2014)
  12. Esperet y Wiechert (2018)

Bibliografía

[editar]