Un gráfico de De Bruijn . Con el orden de los vértices que se muestra, la partición de los bordes en dos subconjuntos que rodean los lados izquierdo y derecho del dibujo es un diseño de 2 colas de este gráfico.
El diseño de cola de un gráfico determinado se define mediante un orden total de los vértices del gráfico junto con una partición de los bordes en varias "colas". El conjunto de aristas en cada cola es necesario para evitar aristas que estén anidadas correctamente: si ab y cd son dos aristas en la misma cola, entonces no debería ser posible tener a < c < d < b en el orden de los 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, a partir de un diseño de cola, se podrían 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, quitar de la cola todos los bordes para los cuales es el segundo punto final y luego ponerlos en cola. todos los bordes para los cuales es el primer punto final. La condición de anidamiento garantiza que, cuando se alcanza un vértice, todos los bordes para los cuales es el segundo punto final estén listos para ser retirados de la cola. [1] Otra definición equivalente de diseños de cola 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 envolviendo una vez alrededor del cilindro. Los bordes asignados a la misma cola no pueden cruzarse entre sí, pero sí entre bordes que pertenecen a colas diferentes. [2]
Los diseños de cola fueron definidos por Heath y Rosenberg (1992), por analogía con trabajos anteriores sobre la incorporación 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 clasificación de permutaciones utilizando sistemas de colas paralelas, y pueden estar motivados por aplicaciones en el diseño 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 la cola número 1, con un orden de vértices dado por un recorrido en amplitud . [3] Los pseudobosques y los gráficos de cuadrícula también tienen el número de cola 1. [4] Los gráficos externos 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 externo cuyo número de cola es exactamente 2. [5] Los gráficos en series paralelas tienen un número de cola como máximo 3, [6] mientras que el número de cola de 3 árboles planos es como máximo 5. [7]
Cada gráfico de 1 cola es un gráfico plano , con una incrustación plana "nivelada en arco" 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 nivelado arqueado tiene un diseño de 1 cola. [11] En 1992, Heath, Leighton y 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. (2020), quienes demostraron que los gráficos planos y, de manera más general, toda clase de gráficos menores cerrados tienen un número de cola acotado. En particular, Dujmović et al. (2020) demostraron que el número de cola de gráficos planos es como máximo 49, límite que Bekos, Gronemann y Raftopoulou (2021) redujeron a 42.
Usando una variación del número de cola llamada número de cola fuerte, el número de cola de un producto gráfico puede estar limitado por una función de los números de cola y los números de cola fuerte de los factores del producto. [12]
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, [13] y, de manera más general, los gráficos con un número de cola q tienen como máximo 2 qn – q (2 q + 1) aristas . [14] Esto implica que estos gráficos también tienen un número cromático pequeño : en particular, los gráficos de 1 cola son de 3 colores, y los gráficos con número de cola q pueden necesitar al menos 2 q + 1 y como máximo 4 q colores. [14] 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 . [15] Este límite es casi ajustado, porque para gráficos aleatorios d -regulares el número de cola es, con alta probabilidad,
[dieciséis]
Problema no resuelto en matemáticas :
¿Todos los gráficos con un número de cola acotado también deben tener un grosor de libro acotado y viceversa?
Los gráficos con número de cola 1 tienen un grosor de libro como máximo 2. [17]
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. [18]
El grosor del libro puede ser mucho mayor que el número de cola: los gráficos ternarios de Hamming tienen un número de cola logarítmico pero un grosor de libro polinomialmente grande [18] y hay gráficos con número de cola 4 que tienen un grosor de libro arbitrariamente grande. [17] Heath, Leighton y Rosenberg (1992) conjeturaron que el número de cola es como máximo una función lineal del espesor 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 un grosor de libro acotado tienen un número de cola acotado. [19]
Ganley y Heath (2001) preguntaron si el número de cola de un gráfico podría acotarse en función del ancho de su árbol y citaron un Ph.D. La disertación de SV Pemmaraju proporciona evidencia de que la respuesta era no: a partir de esta evidencia , los árboles planos 3 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. [20]
Complejidad computacional
Es NP-completo determinar el número de cola de un gráfico determinado, o incluso probar si este número es 1. [21]
Sin embargo, si el orden de los vértices de un diseño de cola se proporciona como parte de la entrada, entonces el número óptimo de colas para el diseño es igual al número máximo de aristas en un k -arcoíris , un conjunto de k aristas, cada dos de las cuales forman un par anidado. Se puede realizar una partición de aristas en colas asignando una arista e que sea la arista exterior de un i- arcoíris (y no de un arcoíris más grande) a la i- ésima cola. 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. [22]
Los gráficos de número de cola acotado también tienen expansión acotada , lo que significa que sus menores poco profundos son gráficos dispersos con una proporción de aristas a vértices (o equivalentemente degeneración o arboricidad ) que está limitada por una función del número de cola y la profundidad del menor. Como consecuencia, varios problemas algorítmicos, incluido el isomorfismo de subgrafos para gráficos de patrones de tamaño acotado, tienen algoritmos de tiempo lineal para estos gráficos. [23] De manera más general, debido a su expansión acotada, es posible verificar si cualquier 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. [24]
Aplicación en dibujo gráfico.
Aunque los diseños de cola no necesariamente producen buenos dibujos de gráficos bidimensionales , se han utilizado para el dibujo de gráficos tridimensionales. En particular, una clase de gráfico 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 rectos). [25] Así, por ejemplo, los gráficos de De Bruijn , los gráficos de ancho de árbol acotado, los gráficos planos y las familias de gráficos menores cerrados adecuados tienen incrustaciones tridimensionales de volumen lineal. [26] [27] [28]
Notas
^ abc 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).
^ Alam y col. (2020).
^ 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
^ ab Dujmović y madera (2004).
^ Heath, Leighton y Rosenberg (1992). Shahrokhi y Shi (2000) proporcionan un algoritmo de tiempo polinomial para encontrar un diseño con tantas colas. Dujmović y Wood (2004) mejoraron el factor constante en este límite , donde e es la base del logaritmo natural .
^ Heath, Leighton y Rosenberg (1992); Madera (2008).
^ ab Dujmović y otros. (2022)
^ ab Heath, Leighton y Rosenberg (1992).
^ Dujmović y madera (2005).
^ Dujmović y Wood (2003); Dujmović, Morin y Wood (2005). Véase Wood (2002) para obtener un resultado preliminar más débil, limitando 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 Méndez y Wood (2012); Nešetřil y Ossona de Méndez (2012), págs. 321–327.
^ Nešetřil y Ossona de Méndez (2012), Teorema 18.2, p. 401.
^ Madera (2002); Dujmović, Por & Wood (2004); Dujmović, Morin y Wood (2005). Consulte Di Giacomo y Meijer (2004) para conocer límites más estrictos en las dimensiones de la cuadrícula para gráficos de números de cola pequeños.
^ Dujmović y madera (2003)
^ Dujmović, Morin y Wood (2005)
^ Dujmović y otros. (2020)
Referencias
Auer, Cristóbal; Bachmaier, cristiano; Brandeburgo, Francisco José; Brunner, Wolfgang; Gleißner, Andreas (2011), "Plane drawings of queue and deque Graphs", Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Alemania, 21 al 24 de septiembre de 2010, artículos seleccionados revisados , Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, págs. 68–79, doi : 10.1007/978-3-642-18469-7_7 , ISBN 978-3-642-18468-0, señor 2781254.
Alam, Jawaherul Md.; Bekos, Michael A.; Gronemann, Martín; Kaufmann, Michael; Pupyrev, Sergey (2020), "Diseños de cola de 3 árboles planos", Algorithmica , 9 (82): 2564–2585, arXiv : 1808.10841 , doi : 10.1007/s00453-020-00697-4, S2CID 52143414.
Bekos, Michael A.; Gronemann, Martín; Raftopoulou, Chrysanthi N. (2021), "On the Queue Number of Planar Graphs", Dibujo de gráficos: 29.º Simposio internacional, GD 2021, Tubinga, Alemania, 14 al 17 de septiembre de 2021, artículos seleccionados revisados , apuntes de conferencias sobre informática, Heidelberg: Springer.
Di Battista, Giuseppe; Frati, Fabricio; Pach, János (2013), "Sobre el número de cola de gráficos planos" (PDF) , SIAM Journal on Computing , 42 (6): 2243–2285, doi :10.1137/130908051, MR 3141759.
Di Giacomo, Emilio; Meijer, Henk (2004), "Seguimiento de dibujos de gráficos con número de cola constante", Dibujo de gráficos: 11.º Simposio internacional, GD 2003 Perugia, Italia, 21 al 24 de septiembre de 2003 Artículos revisados , Apuntes de conferencias en informática, vol. 2912, Berlín: Springer, págs. 214–225, doi : 10.1007/978-3-540-24595-7_20 , ISBN 978-3-540-20831-0, señor 2177595.
Dujmović, Vida ; Morín, Pat ; Wood, David R. (2013), "Separadores en capas para diseños de colas, dibujo de gráficos 3D y coloración no repetitiva", Actas del 54º Simposio IEEE sobre fundamentos de la informática (FOCS '13) , págs. 280–289, arXiv : 1306.1595 , doi :10.1109/FOCS.2013.38, S2CID 5613857.
Dujmović, Vida ; Por, Atila; Wood, David R. (2004), "Diseños de seguimiento de gráficos" (PDF) , Matemáticas discretas e informática teórica , 6 (2): 497–521, arXiv : cs/0407033 , Bibcode : 2004cs...... ..7033D, SEÑOR 2180055.
Dujmović, Vida ; Wood, David R. (2003), "Particiones de árboles de k -árboles con aplicaciones en diseño de gráficos", Conceptos teóricos de grafos en informática: 29º taller internacional, WG 2003. Elspeet, Países Bajos, 19 al 21 de junio de 2003 Artículos revisados , Apuntes de conferencias sobre informática, vol. 2880, Berlín: Springer, págs. 205–217, CiteSeerX 10.1.1.130.1914 , doi :10.1007/978-3-540-39890-5_18, ISBN 978-3-540-20452-7, SEÑOR 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, doi :10.46298/dmtcs.346, MR 2164064.
Ganley, José L.; Heath, Lenwood S. (2001), "El número de página de k -trees 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), "Sobre el número de cola del hipercubo", Notas electrónicas en matemáticas discretas , 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", Revista SIAM de Matemáticas Discretas , 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.
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 "", Cartas sobre procesamiento de información , 108 (3): 107–109, doi :10.1016/j.ipl.2008.04.019, MR 2452135.
Rengarajan, S.; Veni Madhavan, CE (1995), "Stack and queue number of 2-trees", Computing and Combinatorics: First Annual International Conference, COCOON '95 Xi'an, China, 24 al 26 de agosto de 1995, Actas , Apuntes de conferencias sobre informática Ciencia, vol. 959, Berlín: Springer, págs. 203–212, doi :10.1007/BFb0030834, ISBN 978-3-540-60216-3, SEÑOR 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 de software y la informática teórica, 22ª Conferencia Kanpur, India, 12 al 14 de diciembre de 2002 , Actas , Apuntes de conferencias sobre informática, vol. 2556, Berlín: Springer, págs. 348–359, doi :10.1007/3-540-36206-1_31, ISBN 978-3-540-00225-3, señor 2046017.
Wood, David R. (2005), "Diseños de cola de potencias y productos gráficos" (PDF) , Matemáticas discretas e informática teórica , 7 (1): 255–268, doi :10.46298/dmtcs.352, MR 2183176, S2CID 2361133.
Wood, David R. (2008), "Los gráficos de grados acotados tienen un número de cola arbitrariamente grande", Matemáticas discretas e informática teórica , 10 (1): 27–34, arXiv : math/0601293 , Bibcode : 2006math... ...1293W.
enlaces externos
Diseños de pila y cola, problemas presentados en el verano de 2009, experiencias de investigación para estudiantes de posgrado, Douglas B. West
