En matemáticas, el número de cola de un gráfico es un gráfico invariante definido de manera análoga al número de pila (grosor del libro) utilizando ordenaciones primero en entrar, primero en salir (cola) en lugar de las últimas en entrar, primero en salir (pila).
Definición
Un diseño de cola de un gráfico dado se define por un orden total de los vértices del gráfico junto con una partición de los bordes en una serie de "colas". El conjunto de aristas en cada cola es necesario para evitar aristas que estén correctamente anidadas: si ab y cd son dos aristas en la misma cola, entonces no debería ser posible tener a < c < d < b en el ordenamiento de vértices. El número de cola qn ( G ) de un gráfico G es el número mínimo de colas en un diseño de cola. [1]
De manera equivalente, desde un diseño de cola, uno podría procesar los bordes en una sola cola usando una estructura de datos de cola , considerando los vértices en su orden dado, y al llegar a un vértice, quitando de la cola todos los bordes para los cuales es el segundo punto final seguido de enqueueing todos los bordes para los que es el primer punto final. La condición de anidamiento asegura que, cuando se alcanza un vértice, todos los bordes para los que es el segundo punto final están listos para ser quitados de la cola. [1] Otra definición equivalente de diseño de colas implica incrustaciones del gráfico dado en un cilindro , con los vértices colocados en una línea en el cilindro y con cada borde envuelto una vez alrededor del cilindro. Los bordes que están asignados a la misma cola no pueden cruzarse entre sí, pero se permiten cruces entre bordes que pertenecen a diferentes colas. [2]
Los diseños de colas fueron definidos por Heath y Rosenberg (1992) , por analogía con trabajos anteriores sobre incrustaciones de gráficos en libros , que se pueden definir de la misma manera utilizando pilas en lugar de colas. Como observaron, estos diseños también están relacionados con trabajos anteriores sobre la clasificación de permutaciones utilizando sistemas de colas paralelas, y pueden estar motivados por aplicaciones en el diseño de VLSI y en la gestión de comunicaciones para algoritmos distribuidos . [1]
Clases de gráficos con número de cola acotado
Cada árbol tiene el número de cola 1, con un orden de vértice dado por un recorrido en anchura . [3] Los pseudoforestes y los gráficos de cuadrícula también tienen un número de cola 1. [4] Los gráficos exteriores tienen un número de cola como máximo 2; el gráfico de 3 soles (un triángulo con cada uno de sus bordes reemplazado por un triángulo) es un ejemplo de un gráfico plano exterior cuyo número de cola es exactamente 2. [5] Los gráficos en serie-paralelos tienen un número de cola como máximo 3. [6]
Los gráficos binarios de Bruijn tienen un número de cola 2. [7] El gráfico de hipercubo d- dimensional tiene un número de cola como máximo. [8] Los números de cola de los gráficos completos K n y los gráficos bipartitos completos K a , b se conocen exactamente: son y respectivamente. [9]
Cada gráfico de 1 cola es un gráfico plano , con una incrustación plana "arqueada nivelada" en la que los vértices se colocan en líneas paralelas (niveles) y cada borde conecta vértices en dos niveles consecutivos o forma un arco que conecta dos vértices en el mismo nivel recorriendo todos los niveles anteriores. Por el contrario, cada gráfico plano arqueado nivelado tiene un diseño de 1 cola. [10] En 1992, Heath, Leighton & Rosenberg (1992) conjeturaron que todo gráfico plano tiene un número de cola acotado. Esta conjetura fue resuelta positivamente en 2019 por Dujmović et al. (2019) quienes demostraron que los gráficos planos y, de manera más general, todas las clases de gráficos cerrados menores propios tienen un número de cola acotado.
Utilizando una variación del número de cola llamado número de cola fuerte, el número de cola de un producto gráfico puede estar delimitado por una función de los números de cola y los números de cola fuerte de los factores del producto. [11]
Invariantes relacionados
Los gráficos con un número de cola bajo son gráficos dispersos : los gráficos de 1 cola con n vértices tienen como máximo 2 n - 3 aristas, [12] y más generalmente los gráficos con un número de cola q tienen como máximo 2 qn - q (2 q + 1) aristas . [13] Esto implica que estos gráficos también tienen un número cromático pequeño : en particular, los gráficos de 1 cola se pueden colorear en 3, y los gráficos con el número de cola q pueden necesitar al menos 2 q + 1 y como máximo 4 q colores. [13] En la otra dirección, un límite en el número de aristas implica un límite mucho más débil en el número de cola: los gráficos con n vértices y m aristas tienen un número de cola como máximo O ( √ m ). [14] Este límite es casi estrecho, porque para gráficos d -regulares aleatorios el número de cola es, con alta probabilidad,
- [15]
¿Todos los gráficos con número de cola acotado también deben tener un grosor de libro acotado y viceversa?
Los gráficos con el número de cola 1 tienen un grosor de libro como máximo 2. [16] Para cualquier orden de vértice fijo, el producto del grosor del libro y los números de cola para ese orden es al menos tan grande como el ancho de corte del gráfico dividido por su grado máximo. [17] El grosor del libro puede ser mucho mayor que el número de cola: los gráficos de Hamming ternarios tienen un número de cola logarítmico pero un grosor de libro polinomialmente grande [17] y hay gráficos con número de cola 4 que tienen un grosor de libro arbitrariamente grande. [16] Heath, Leighton y Rosenberg (1992) conjeturaron que el número de la cola es como mucho una función lineal del grosor del libro, pero no se conoce ningún límite funcional en esta dirección. Se sabe que, si todos los gráficos bipartitos con incrustaciones de libros de 3 páginas tienen un número de cola acotado, entonces todos los gráficos con grosor de libro acotado tienen un número de cola acotado. [18]
Ganley y Heath (2001) preguntaron si el número de cola de un gráfico podría limitarse en función de su ancho de árbol , y citaron un Ph.D. disertación de SV Pemmaraju como evidencia de que la respuesta era no: a partir de esta evidencia, los 3 árboles planos parecían tener un número de cola ilimitado. Sin embargo, posteriormente se demostró que el número de cola estaba limitado por una función (doblemente exponencial) del ancho del árbol. [19]
Complejidad computacional
Es NP-completo para determinar el número de cola de un gráfico dado, o incluso para probar si este número es uno. [20]
Sin embargo, si el orden de vértice de un diseño de cola se da como parte de la entrada, entonces el número óptimo de colas para el diseño es igual al número máximo de bordes en un k -arco iris, un conjunto de k bordes cada dos de los cuales forman un par anidado. Se puede realizar una partición de bordes en colas asignando un borde e que es el borde exterior de un arco iris en i (y de un arco iris no más grande) a la cola i- ésima. Es posible construir un diseño óptimo en el tiempo O ( m log log n ) , donde n denota el número de vértices del gráfico de entrada y m denota el número de aristas. [21]
Los gráficos de número de cola acotado también tienen expansión acotada , lo que significa que sus menores superficiales son gráficos dispersos con una relación de aristas a vértices (o equivalentemente degeneración o arboricidad ) que está delimitada por una función del número de cola y la profundidad del menor. Como consecuencia, varios problemas algorítmicos, incluido el isomorfismo de subgráficos para gráficos de patrones de tamaño acotado, tienen algoritmos de tiempo lineal para estos gráficos. [22] De manera más general, debido a su expansión acotada, es posible comprobar si alguna oración en la lógica de primer orden de los gráficos es válida para un gráfico dado de número de cola acotado, en tiempo lineal. [23]
Aplicación en el dibujo de gráficos
Aunque los diseños de colas no producen necesariamente buenos dibujos de gráficos bidimensionales , se han utilizado para el dibujo de gráficos tridimensionales. En particular, un gráfico de clase X tiene un número de cola acotado si y solo si para cada gráfico de n -vértices G en X , es posible colocar los vértices de G en una cuadrícula tridimensional de dimensiones O ( n ) × O (1 ) × O (1) para que no se crucen dos bordes (cuando se dibujan en línea recta). [24] Así, por ejemplo, los gráficos de Bruijn, los gráficos de ancho de árbol acotado, los gráficos planos y las familias de gráficos cerrados menores adecuados tienen incrustaciones tridimensionales de volumen lineal. [25] [26] [27]
Notas
- ↑ a b c Heath y Rosenberg (1992) .
- ^ Auer y col. (2011) .
- ^ Heath y Rosenberg (1992) , Proposición 4.1.
- ^ Heath y Rosenberg (1992) , proposiciones 4.2 y 4.3.
- ^ Heath, Leighton y Rosenberg (1992) ; Rengarajan y Veni Madhavan (1995) .
- ^ Rengarajan y Veni Madhavan (1995) .
- ^ Heath y Rosenberg (1992) , Proposición 4.6.
- ↑ Gregor, Škrekovski y Vukašinović (2012)
- ^ Heath y Rosenberg (1992) , proposiciones 4.7 y 4.8.
- ^ Heath y Rosenberg (1992) , Teorema 3.2.
- ^ Madera (2005) .
- ^ Heath y Rosenberg (1992) , Teorema 3.6
- ↑ a b Dujmović y Wood (2004) .
- ^ Heath, Leighton y Rosenberg (1992) . Shahrokhi y Shi (2000) dan un algoritmo de tiempo polinomial para encontrar un diseño con cerca de este número de colas. Dujmović y Wood (2004) mejoraron el factor constante en este límite a e √ m , donde e es la base del logaritmo natural .
- ^ Heath, Leighton y Rosenberg (1992) ; Madera (2008) .
- ^ a b Dujmović y col. (2020)
- ↑ a b Heath, Leighton y Rosenberg (1992) .
- ^ Dujmović y Wood (2005) .
- ^ Dujmović y Wood (2003) ; Dujmović, Morin y Wood (2005) . Consulte Wood (2002) para obtener un resultado preliminar más débil, delimitando el número de cola por el ancho de ruta o por una combinación de ancho de árbol y grado.
- ^ Heath y Rosenberg (1992) , Corolario 3.9.
- ^ Heath y Rosenberg (1992) , Teorema 2.3.
- ^ Nešetřil, Ossona de Mendez y Wood (2012) ; Nešetřil y Ossona de Mendez (2012) , págs. 321–327.
- ^ Nešetřil y Ossona de Mendez (2012) , Teorema 18.2, p. 401.
- ^ Madera (2002) ; Dujmović, Pór & Wood (2004) ; Dujmović, Morin y Wood (2005) . Consulte Di Giacomo y Meijer (2004) para obtener límites más estrictos en las dimensiones de la cuadrícula para gráficos de números de cola pequeños.
- ^ Dujmović y Wood (2003)
- ^ Dujmović, Morin y Wood (2005)
- ^ Dujmović y col. (2019)
Referencias
- Auer, Christopher; Bachmaier, Christian; Brandeburgo, Franz Josef; Brunner, Wolfgang; Gleißner, Andreas (2011), "Plane drawings of queue and deque graphs", Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, 21-24 de septiembre de 2010, Revised Selected Papers , Lecture Notes in Computer Science, 6502 , Heidelberg: Springer, págs. 68–79, doi : 10.1007 / 978-3-642-18469-7_7 , MR 2781254.
- Bekos, Michael A .; Förster, Henry; Gronemann, Martin; Mchedlidze, Tamara; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Ueckerdt, Torsten (2018), "Las gráficas planas de grado acotado tienen un número de cola constante", CoRR 1811.00816 , arXiv : 1811.00816 , Bibcode : 2018arXiv181100816B.
- Di Battista, Giuseppe; Frati, Fabrizio; Pach, János (2013), "On the queue number of planar graphs" (PDF) , SIAM Journal on Computing , 42 (6): 2243–2285, doi : 10.1137 / 130908051 , MR 3141759.
- Di Giacomo, Emilio; Meijer, Henk (2004), "Trazar dibujos de gráficos con número de cola constante", Dibujo de gráficos: 11th International Symposium, GD 2003 Perugia, Italia, 21-24 de septiembre de 2003 Revised Papers , Lecture Notes in Computer Science, 2912 , Berlín: Springer, págs. 214–225, doi : 10.1007 / 978-3-540-24595-7_20 , MR 2177595.
- Dujmović, Vida (2015), "Diseños de gráficos mediante separadores en capas", Journal of Combinatorial Theory , Serie B, 110 : 79–89, arXiv : 1302.0304 , doi : 10.1016 / j.jctb.2014.07.005 , MR 3279388.
- Dujmović, Vida; Eppstein, David ; Hickingbotham, Robert; Morin, Pat ; Wood, David (2020), el número de pila no está limitado por el número de cola , arXiv : 2011.04195.
- Dujmović, Vida; Joret, Gwenäel; Micek, Piotr; Morin, Pat ; Ueckerdt, Torsten; Wood, David R. (2020), "Las gráficas planas tienen un número de cola acotado", Las gráficas planas tienen un número de cola acotado , 67 , págs. 1-38, arXiv : 1904.04791 , doi : 10.1145 / 3385731
- Dujmović, Vida; Morin, Pat ; Wood, David R. (2005), "Diseño de gráficos con ancho de árbol acotado", SIAM Journal on Computing , 34 (3): 553–579, arXiv : cs / 0406024 , doi : 10.1137 / S0097539702416141 , MR 2137079.
- Dujmović, Vida; Morin, Pat ; Wood, David R. (2013), "Separadores en capas para diseños de colas, dibujo de gráficos en 3D y coloración no repetitiva", Actas del 54º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación (FOCS '13) , págs. 280–289, arXiv : 1306.1595 , doi : 10.1109 / FOCS.2013.38.
- Dujmović, Vida; Pór, Atila; Wood, David R. (2004), "Track layouts of graphs" (PDF) , Matemáticas discretas e informática teórica , 6 (2): 497–521, arXiv : cs / 0407033 , Bibcode : 2004cs ...... ..7033D , MR 2180055.
- Dujmović, Vida; Wood, David R. (2003), "Particiones de árboles de k- árboles con aplicaciones en el diseño de gráficos", Conceptos teóricos de gráficos en Ciencias de la Computación: 29th International Workshop, WG 2003. Elspeet, Países Bajos, 19-21 de junio de 2003 .Revised Papers , Lecture Notes in Computer Science, 2880 , Berlín: Springer, págs. 205–217, doi : 10.1007 / 978-3-540-39890-5_18 , MR 2080081.
- Dujmović, Vida; Wood, David R. (2004), "Sobre diseños lineales de gráficos" (PDF) , Matemáticas discretas e informática teórica , 6 (2): 339–357, MR 2081479.
- Dujmović, Vida; Wood, David R. (2005), "Pilas, colas y pistas: diseños de subdivisiones de gráficos" (PDF) , Matemáticas discretas e informática teórica , 7 (1): 155-201, MR 2164064.
- Ganley, Joseph L .; Heath, Lenwood S. (2001), "El número de páginas de k -árboles es O ( k )", Matemáticas aplicadas discretas , 109 (3): 215-221, doi : 10.1016 / S0166-218X (00) 00178-5 , Señor 1818238.
- Gregor, Petr; Škrekovski, Riste; Vukašinović, Vida (2011), "On the queue-number of the hypercube", Electronic Notes in Discrete Mathematics , 38 : 413–418, doi : 10.1016 / j.endm.2011.09.067.
- Gregor, Petr; Škrekovski, Riste; Vukašinović, Vida (2012), "Diseños de cola de hipercubos", SIAM Journal on Discrete Mathematics , 26 (1): 77–88, CiteSeerX 10.1.1.417.7129 , doi : 10.1137 / 100813865.
- Hasunuma, Toru; Hirota, Misa (2007), "Un límite superior mejorado en el número de cola del hipercubo", Information Processing Letters , 104 (2): 41–44, doi : 10.1016 / j.ipl.2007.05.006 , MR 2343263.
- Heath, Lenwood S .; Leighton, Frank Thomson ; Rosenberg, Arnold L. (1992), "Comparación de colas y pilas como mecanismos para diseñar gráficos", SIAM Journal on Discrete Mathematics , 5 (3): 398–412, doi : 10.1137 / 0405031 , MR 1172748.
- Heath, Lenwood S .; Rosenberg, Arnold L. (1992), "Trazado de gráficos mediante colas", SIAM Journal on Computing , 21 (5): 927–958, doi : 10.1137 / 0221055 , MR 1181408.
- Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, 28 , Springer, doi : 10.1007 / 978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
- Nešetřil, Jaroslav ; Ossona de Méndez, Patrice ; Wood, David R. (2012), "Caracterizaciones y ejemplos de clases de gráficos con expansión acotada", European Journal of Combinatorics , 33 (3): 350–373, arXiv : 0902.3265 , doi : 10.1016 / j.ejc.2011.09.008 , MR 2864421.
- Pai, Kung-Jui; Chang, Jou-Ming; Wang, Yue-Li (2008), "Una nota sobre" Un límite superior mejorado en el número de cola del hipercubo " ", Information Processing Letters , 108 (3): 107-109, doi : 10.1016 / j.ipl.2008.04. 019 , MR 2452135.
- Rengarajan, S .; Veni Madhavan, CE (1995), "Número de pila y cola de 2 árboles", Computación y combinatoria: Primera Conferencia Internacional Anual, COCOON '95 Xi'an, China, 24 al 26 de agosto de 1995, Actas , Notas de la conferencia en computadora Science, 959 , Berlín: Springer, págs. 203–212, doi : 10.1007 / BFb0030834 , MR 1450116.
- Shahrokhi, Farhad; Shi, Weiping (2000), "Sobre conjuntos cruzados, conjuntos disjuntos y número de página", Journal of Algorithms , 34 (1): 40–53, doi : 10.1006 / jagm.1999.1049 , MR 1732197.
- Wood, David R. (2002), "Diseños de cola, ancho de árbol y dibujo de gráficos tridimensionales", FST TCS 2002: Fundamentos de la tecnología del software y la informática teórica, 22ª Conferencia Kanpur, India, 12 al 14 de diciembre de 2002 , Actas , Lecture Notes in Computer Science, 2556 , Berlín: Springer, págs. 348–359, doi : 10.1007 / 3-540-36206-1_31 , MR 2046017.
- Wood, David R. (2005), "Diseños de colas de productos y potencias de gráficos" (PDF) , Matemáticas discretas e informática teórica , 7 (1): 255-268, MR 2183176.
- Wood, David R. (2008), "Los gráficos de grados acotados tienen un número de cola arbitrariamente grande" , Matemáticas discretas y Ciencias de la computación teóricas , 10 (1): 27–34, arXiv : math / 0601293 , Bibcode : 2006math ... ... 1293W.
enlaces externos
- Disposición de pilas y colas , problemas presentados en el verano de 2009, experiencias de investigación para estudiantes graduados, Douglas B. West