Dimensión de gráfico de intervalo

En la teoría de grafos, la dimensión de intervalo de un gráfico  es un gráfico invariante introducido por Fred S. Roberts en 1969.

La dimensión de intervalo de un gráfico es la dimensión mínima en la que un gráfico dado se puede representar como un gráfico de intersecciones de hiperrectángulos (es decir, paralelepípedos rectangulares multidimensionales) con bordes paralelos a los ejes. Es decir, debe haber una correspondencia uno a uno entre los vértices del gráfico y un conjunto de hiperrectángulos, tal que los rectángulos se intersecan si y solo si hay un borde que conecta los vértices correspondientes.

Ejemplos

La figura muestra un gráfico con seis vértices y una representación de este gráfico como un gráfico de intersección de rectángulos (bidimensionales ordinarios). Este gráfico no se puede representar como un gráfico de intersecciones de rectángulos de menor dimensión (en este caso, segmentos), por lo que la dimensión del intervalo del gráfico es dos.

Roberts [1] demostró que un gráfico de 2n vértices formado al eliminar una coincidencia perfecta de un gráfico completo de 2n vértices tiene una dimensión de intervalo exactamente n  : cualquier par de vértices no conectados debe representarse como hiperrectángulos, que deben estar separados de una manera diferente a otro par de dimensiones. La representación hiperrectángulo de este gráfico con dimensión exactamente n se puede encontrar engrosando cada una de las 2n caras del hipercubo n - dimensional en un hiperrectángulo. A raíz de este resultado, tales grafos comenzaron a llamarse grafos de Roberts [2] , aunque son más conocidos como grafos de “partido” y también pueden ser tratados como grafos de Turan T (2 n , n ).

Relación con otras clases de grafos

Un gráfico tiene una dimensión de intervalo como máximo uno si y sólo si es un gráfico de intervalo . La dimensión de intervalo de un gráfico arbitrario G  es el número mínimo de gráficos de intervalo con el mismo conjunto de vértices (como G ) tal que la intersección de los conjuntos de aristas de los gráficos de intervalo da G. Cualquier gráfico plano exterior tiene una dimensión de intervalo como máximo dos [3] , y cualquier gráfico plano tiene una dimensión de intervalo como máximo tres [4] .

Si un gráfico bipartito tiene una dimensión de intervalo de dos, se puede representar como un gráfico de intersecciones de segmentos paralelos a los ejes en el plano [5] .

Resultados algorítmicos

Muchos problemas de gráficos se pueden resolver o aproximar de manera más eficiente en gráficos con una dimensión de intervalo limitada. Por ejemplo, el problema de la camarilla más grande se puede resolver en tiempo polinomial para gráficos con una dimensión de intervalo limitada [6] . Para algunos otros problemas de grafos, se puede encontrar una solución o aproximación eficiente si la representación es en forma de una intersección de hipermogoedros de baja dimensión [7] .

Sin embargo, encontrar tales representaciones puede ser difícil: verificar si la dimensión del intervalo de un gráfico dado excede algún valor predeterminado K es un problema NP-completo , incluso para K = 2 [8] . Chandran, Francis y Sivadasan [9] describieron algoritmos para encontrar representaciones gráficas de intersección hiperrectángulo de gráficos arbitrarios con una dimensión que está dentro del factor logarítmico de la mayor potencia del gráfico . Este resultado da un límite superior en la dimensión del intervalo del gráfico.

A pesar de la dificultad para los parámetros naturales, la dimensión del intervalo de un gráfico es un problema solucionable de parámetro fijo si la parametrización se lleva a cabo de acuerdo con el número de cobertura de vértice del gráfico de entrada [10] .

Notas

  1. ↑ Roberts, 1969 .
  2. ↑ Por ejemplo, véanse los artículos de Chandran, Francis y Sivadasan (2010 ), Chandran y Sivadasan Chandran, Sivadasan (2007 ).
  3. ↑ Scheinerman, 1984 .
  4. ↑ Thomassen, 1986 .
  5. ↑ Bellantoni, Hartman, Przytycka, Whitesides, 1993 .
  6. ↑ Chandran, Francis y Sivadasan (2010 ) señalaron que esto se deriva del hecho de que estos gráficos tienen un número polinomial de camarillas máximas . La representación explícita como una intersección de hiperrectángulos no requiere la enumeración de todas las camarillas máximas.
  7. ↑ Ver, por ejemplo, Agarwal, van Kreveld, Suri (1998 ) y Berman, DasGupta, Muthukrishnan, Ramaswami (2001 ) para aproximaciones de conjuntos independientes más grandes para gráficos de intersección de rectángulos, y Chlebík, Chlebíková (2005 ) para una discusión sobre la dificultad de aproximando estos problemas para grandes dimensiones
  8. ↑ Cozzens (1981 ) mostró que calcular la dimensión del intervalo de un gráfico es un problema NP-completo. Yannakakis (1982 ) demostró que incluso verificar si la dimensión del intervalo no excede 3 es NP-difícil. Finalmente, Kratochvíl (1994 ) mostró que reconocer una dimensión de intervalo = 2 es un problema NP-difícil.
  9. ↑ Chandran, Francisco, Sivadasan, 2010 .
  10. ↑ Adiga, Chitnis, Saurabh, 2010 .

Literatura