En teoría de grafos , la boxicidad es un invariante de grafos , introducido por Fred S. Roberts en 1969.
La boxicidad 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 intersección de cuadros de ejes paralelos . Es decir, debe existir una correspondencia uno a uno entre los vértices del gráfico y un conjunto de cajas, de manera que dos cajas se crucen si y solo si hay una arista que conecta los vértices correspondientes.
Ejemplos de
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 (cajas bidimensionales). Este gráfico no se puede representar como un gráfico de intersección de cajas en cualquier dimensión inferior, por lo que su boxicidad es dos.
Roberts (1969) mostró que el gráfico con 2 n vértices formado al eliminar una coincidencia perfecta de un gráfico completo en 2 n vértices tiene una boxicidad exactamente n : cada par de vértices desconectados debe estar representado por cajas que están separadas en una dimensión diferente a la de cada uno. otro par. Se puede encontrar una representación de caja de este gráfico con una dimensión exactamente n al engrosar cada una de las 2 n facetas de un hipercubo n- dimensional en una caja. Por estos resultados, este gráfico se ha denominado gráfico de Roberts , [1] aunque es más conocido como gráfico cóctel y también puede entenderse como el gráfico de Turán T (2 n , n ).
Relación con otras clases de gráficos
Un gráfico tiene boxicidad como máximo uno si y solo si es un gráfico de intervalo ; la boxicity de un gráfico arbitrario G es el número mínimo de grafo de intervalos en el mismo conjunto de vértices de tal manera que la intersección de los bordes conjuntos de los gráficos intervalo es G . Cada gráfico plano exterior tiene boxicidad como máximo dos, [2] y cada gráfico plano tiene boxicidad como máximo tres. [3]
Si un gráfico bipartito tiene boxicidad dos, se puede representar como un gráfico de intersección de segmentos de líneas paralelas a ejes en el plano. [4]
Adiga, Bhowmick & Chandran (2011) demostraron que la boxicidad de un gráfico 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 partito conjunto de G , el conjunto de elementos maximales corresponde a la segunda serie partite 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 P parcialmente ordenado de altura dos está dentro de un factor 2 de la boxicidad de la gráfica de comparabilidad de P (que es bipartita, ya que P tiene una altura de dos).
Resultados algorítmicos
Muchos problemas de gráficos se pueden resolver o aproximar de manera más eficiente para gráficos con boxicidad acotada que para otros gráficos; por ejemplo, el problema de la camarilla máxima se puede resolver en tiempo polinomial para gráficas con boxicidad acotada. [5] Para algunos otros problemas de gráficos, 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 boxicidad de un gráfico dado es como máximo algún valor dado K , incluso para K = 2. [7] Chandran, Francis & Sivadasan ( 2010) describen algoritmos para encontrar representaciones de gráficos arbitrarios como gráficos de intersección de cajas, con una dimensión que está dentro de un factor logarítmico del grado máximo del gráfico; este resultado proporciona un límite superior en la boxicidad del gráfico.
A pesar de ser difícil por su parámetro natural, la boxicidad es manejable con parámetro fijo cuando se parametriza por el número de cobertura de vértice del gráfico de entrada. [8]
Límites
Si una gráfica G tiene m aristas, entonces:. [9] [10]
Si una gráfica G es k - degenerada (con) y tiene n vértices, entonces G tiene boxicidad. [11]
Si un gráfico G no tiene un gráfico completo en t vértices como menor , entonces[12] mientras que hay gráficos sin un gráfico completo en t vértices como menor , y con boxicidad. [13] En particular, cualquier gráfico G hax boxicidad, dónde denota el invariante Colin de Verdière de G .
Invariantes gráficos relacionados
- La cubicidad se define de la misma manera que la boxicidad pero con hipercubos paralelos al eje en lugar de hiperrectángulos. La boxicidad es una generalización de la cubicidad.
- La esfericidad se define de la misma manera que la boxicidad pero con esferas de diámetro unitario.
Notas
- ^ Por ejemplo, véanse Chandran, Francis y Sivadasan (2010) y Chandran y Sivadasan (2007) .
- ^ Scheinerman (1984) .
- ^ Thomassen (1986) .
- ^ Bellantoni y col. (1993) .
- ^ Chandran, Francis y Sivadasan (2010) observan que esto se deriva del hecho de que estos gráficos tienen un número polinomial de camarillas máximas . No se necesita una representación de caja explícita para enumerar todas las camarillas máximas de manera eficiente.
- ^ Ver, por ejemplo, Agarwal, van Kreveld & Suri (1998) y Berman et al. (2001) para aproximaciones al conjunto máximo independiente para gráficas de intersección de rectángulos, y Chlebík & Chlebíková (2005) para resultados sobre dureza de aproximación de estos problemas en dimensiones superiores.
- ^ Cozzens (1981) muestra que calcular la boxicidad es NP-completo; Yannakakis (1982) muestra que incluso comprobar si la boxicidad es como máximo 3 es NP-difícil; finalmente, Kratochvil (1994) mostró que reconocer la boxicidad 2 es NP-difícil.
- ^ Adiga, Chitnis y Saurabh (2010) .
- ^ Chandran, Francis y Sivadasan (2010)
- ↑ Esperet (2016)
- ^ Adiga, Chandran y Mathew (2014)
- ^ Esperet y Wiechert (2018)
- ↑ Esperet (2016)
Referencias
- 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), "Algoritmos parametrizados para la boxicidad", Algoritmos y Computación: 21er Simposio Internacional, ISAAC 2010, Isla de Jeju, Corea, 15-17 de diciembre de 2010, Actas, Parte I (PDF) , Notas de conferencias en Ciencias de la Computación , 6506 , págs. 366–377, doi : 10.1007 / 978-3-642-17517-6_33 , archivado desde el original (PDF) el 2017-08-30 , consultado el 2018-01-22
- Agarwal, Pankaj K .; van Kreveld, Marc; Suri, Subhash (1998), "Colocación de etiquetas por conjunto máximo independiente en rectángulos", Teoría y aplicaciones de la geometría computacional , 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), "Algoritmos de aproximación eficientes para problemas de empaquetamiento y mosaico con rectángulos", J. Algorithms , 41 (2): 443–470, doi : 10.1006 / jagm.2001.1188.
- Chandran, L. Sunil; Francis, Mathew C .; Sivadasan, Naveen (2010), "Representación geométrica de gráficos en baja dimensión utilizando cajas paralelas de ejes", Algorithmica , 56 (2): 129-140, arXiv : cs.DM/0605013 , doi : 10.1007 / s00453-008-9163- 5 , MR 2.576.537 , S2CID 17838951.
- Chandran, L. Sunil; Sivadasan, Naveen (2007), "Boxicity and treewidth", Journal of Combinatorial Theory , Serie B , 97 (5): 733–744, arXiv : math.CO/0505544 , doi : 10.1016 / j.jctb.2006.12.004 , S2CID 9854207.
- Chlebík, Miroslav; Chlebíková, Janka (2005), "Dureza de aproximación de problemas de optimización en gráficos de intersección de cajas d- dimensionales", Actas del Decimosexto Simposio Anual ACM-SIAM sobre Algoritmos Discretos , págs. 267–276.
- Cozzens, MB (1981), Análogos superiores y multidimensionales de gráficos de intervalo , Ph.D. tesis, Universidad de Rutgers.
- Esperet, Louis (2016), "Boxicidad e invariantes topológicos", European Journal of Combinatorics , 51 : 495–499, arXiv : 1503.05765 , doi : 10.1016 / j.ejc.2015.07.020 , S2CID 5548385.
- Esperet, Louis; Wiechert, Veit (2018), "Boxicidad, dimensión poset y menores excluidos" , Electronic Journal of Combinatorics , 25 (4): # P4.51, arXiv : 1804.00850 , doi : 10.37236 / 7787 , S2CID 119148637.
- Kratochvil, Jan (1994), "Un problema de satisfacibilidad planar especial y una consecuencia de su NP-completitud", Matemáticas aplicadas discretas , 52 (3): 233-252, doi : 10.1016 / 0166-218X (94) 90143-0.
- Quest, M .; Wegner, G. (1990), "Caracterización de las gráficas con boxicidad ≤ 2", Matemáticas discretas , 81 (2): 187-192, doi : 10.1016 / 0012-365X (90) 90151-7.
- Roberts, FS (1969), "On the boxicity and cubicity of a graph", en Tutte, WT (ed.), Recent Progress in Combinatorics , Academic Press, págs. 301–310, ISBN 978-0-12-705150-5.
- Scheinerman, ER (1984), clases de intersección y parámetros de intersección múltiple , tesis de doctorado, Universidad de Princeton.
- Thomassen, Carsten (1986), "Representaciones de intervalos de gráficos planos", Journal of Combinatorial Theory, Serie B , 40 : 9-20, doi : 10.1016 / 0095-8956 (86) 90061-4.
- Yannakakis, Mihalis (1982), "La complejidad del problema de dimensión de orden parcial", SIAM Journal on Algebraic and Discrete Methods , 3 (3): 351–358, doi : 10.1137 / 0603036.