Queue number
In the
Definition
A queue layout of a given graph is defined by a
Equivalently, from a queue layout, one could process the edges in a single queue using a
Queue layouts were defined by
Graph classes with bounded queue number
Every
Binary de Bruijn graphs have queue number 2.[8] The d-dimensional hypercube graph has queue number at most .[9] The queue numbers of complete graphs Kn and complete bipartite graphs Ka,b are known exactly: they are and respectively.[10]
Every 1-queue graph is a planar graph, with an "arched leveled" planar embedding in which the vertices are placed on parallel lines (levels) and each edge either connects vertices on two consecutive levels or forms an arch that connects two vertices on the same level by looping around all previous levels. Conversely, every arched leveled planar graph has a 1-queue layout.[11] In 1992, Heath, Leighton & Rosenberg (1992) conjectured that every planar graph has bounded queue number. This conjecture was resolved positively in 2019 by Dujmović et al. (2020) who showed that planar graphs and, more generally, every proper minor-closed class of graphs has bounded queue number. In particular, Dujmović et al. (2020) proved that the queue number of planar graphs is at most 49, a bound which was reduced to 42 by Bekos, Gronemann & Raftopoulou (2021).
Using a variation of queue number called the strong queue number, the queue number of a graph product can be bounded by a function of the queue numbers and strong queue numbers of the factors in the product.[12]
Related invariants
Graphs with low queue number are
Must every graph with bounded queue number also have bounded book thickness, and vice versa?
Graphs with queue number 1 have book thickness at most 2.[17] For any fixed vertex ordering, the product of the book thickness and queue numbers for that ordering is at least as large as the cutwidth of the graph divided by its maximum degree.[18] The book thickness may be much larger than the queue number: ternary Hamming graphs have logarithmic queue number but polynomially-large book thickness[18] and there are graphs with queue number 4 that have arbitrarily large book thickness.[17] Heath, Leighton & Rosenberg (1992) conjectured that the queue number is at most a linear function of the book thickness, but no functional bound in this direction is known. It is known that, if all bipartite graphs with 3-page book embeddings have bounded queue number, then all graphs with bounded book thickness have bounded queue number.[19]
Ganley & Heath (2001) asked whether the queue number of a graph could be bounded as a function of its treewidth, and cited an unpublished Ph.D. dissertation of S. V. Pemmaraju as providing evidence that the answer was no: planar 3-trees appeared from this evidence to have unbounded queue number. However, the queue number was subsequently shown to be bounded by a (doubly exponential) function of the treewidth.[20]
Computational complexity
It is
However, if the vertex ordering of a queue layout is given as part of the input, then the optimal number of queues for the layout equals the maximum number of edges in a k-rainbow, a set of k edges each two of which form a nested pair. A partition of edges into queues can be performed by assigning an edge e that is the outer edge of an i-rainbow (and of no larger rainbow) to the ith queue. It is possible to construct an optimal layout in time O(m log(log n)), where n denotes the number of vertices of the input graph and m denotes the number of edges.[22]
Graphs of bounded queue number also have
Application in graph drawing
Although queue layouts do not necessarily produce good two-dimensional graph drawings, they have been used for three-dimensional graph drawing. In particular, a graph class X has bounded queue number if and only if for every n-vertex graph G in X, it is possible to place the vertices of G in a three-dimensional grid of dimensions O(n) × O(1) × O(1) so that no two edges (when drawn straight) cross each other.[25] Thus, for instance, de Bruijn graphs, graphs of bounded treewidth, planar graphs, and proper minor-closed graph families have three-dimensional embeddings of linear volume.[26][27][28]
Notes
- ^ a b c Heath & Rosenberg (1992).
- ^ Auer et al. (2011).
- ^ Heath & Rosenberg (1992), Proposition 4.1.
- ^ Heath & Rosenberg (1992), Propositions 4.2 and 4.3.
- ^ Heath, Leighton & Rosenberg (1992); Rengarajan & Veni Madhavan (1995).
- ^ Rengarajan & Veni Madhavan (1995).
- ^ Alam et al. (2020).
- ^ Heath & Rosenberg (1992), Proposition 4.6.
- ^ Gregor, Škrekovski & Vukašinović (2012)
- ^ Heath & Rosenberg (1992), Propositions 4.7 and 4.8.
- ^ Heath & Rosenberg (1992), Theorem 3.2.
- ^ Wood (2005).
- ^ Heath & Rosenberg (1992), Theorem 3.6
- ^ a b Dujmović & Wood (2004).
- ^ Heath, Leighton & Rosenberg (1992). A polynomial-time algorithm for finding a layout with close to this many queues is given by Shahrokhi & Shi (2000). Dujmović & Wood (2004) improved the constant factor in this bound to , where eis the base of the natural logarithm.
- ^ Heath, Leighton & Rosenberg (1992); Wood (2008).
- ^ a b Dujmović et al. (2022)
- ^ a b Heath, Leighton & Rosenberg (1992).
- ^ Dujmović & Wood (2005).
- ^ Dujmović & Wood (2003); Dujmović, Morin & Wood (2005). See Wood (2002) for a weaker preliminary result, bounding the queue number by the pathwidth or by a combination of treewidth and degree.
- ^ Heath & Rosenberg (1992), Corollary 3.9.
- ^ Heath & Rosenberg (1992), Theorem 2.3.
- ^ Nešetřil, Ossona de Mendez & Wood (2012); Nešetřil & Ossona de Mendez (2012), pp. 321–327.
- ^ Nešetřil & Ossona de Mendez (2012), Theorem 18.2, p. 401.
- ^ Wood (2002); Dujmović, Pór & Wood (2004); Dujmović, Morin & Wood (2005). See Di Giacomo & Meijer (2004) for tighter bounds on the grid dimensions for graphs of small queue number.
- ^ Dujmović & Wood (2003)
- ^ Dujmović, Morin & Wood (2005)
- ^ Dujmović et al. (2020)
References
- Auer, Christopher; Bachmaier, Christian; Brandenburg, Franz Josef; Brunner, Wolfgang; Gleißner, Andreas (2011), "Plane drawings of queue and deque graphs", Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, pp. 68–79, MR 2781254.
- Alam, Jawaherul Md.; Bekos, Michael A.; Gronemann, Martin; Kaufmann, Michael; Pupyrev, Sergey (2020), "Queue Layouts of Planar 3-Trees", Algorithmica, 9 (82): 2564–2585, S2CID 52143414.
- Bekos, Michael A.; Gronemann, Martin; Raftopoulou, Chrysanthi N. (2021), "On the Queue Number of Planar Graphs", Graph Drawing: 29th International Symposium, GD 2021, Tuebingen, Germany, September 14–17, 2021, Revised Selected Papers, Lecture Notes in Computer Science, Heidelberg: Springer.
- Di Battista, Giuseppe; Frati, Fabrizio; MR 3141759.
- Di Giacomo, Emilio; Meijer, Henk (2004), "Track drawings of graphs with constant queue number", Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21–24, 2003 Revised Papers, Lecture Notes in Computer Science, vol. 2912, Berlin: Springer, pp. 214–225, MR 2177595.
- S2CID 60212.
- S2CID 226281691.
- doi:10.1145/3385731
- S2CID 3264071.
- S2CID 5613857.
- MR 2180055.
- MR 2080081.
- MR 2081479.
- MR 2164064.
- Ganley, Joseph L.; Heath, Lenwood S. (2001), "The pagenumber of k-trees is O(k)", Discrete Applied Mathematics, 109 (3): 215–221, MR 1818238.
- Gregor, Petr; Škrekovski, Riste; Vukašinović, Vida (2011), "On the queue-number of the hypercube", Electronic Notes in Discrete Mathematics, 38: 413–418, .
- Gregor, Petr; Škrekovski, Riste; Vukašinović, Vida (2012), "Queue layouts of hypercubes", SIAM Journal on Discrete Mathematics, 26 (1): 77–88, .
- Hasunuma, Toru; Hirota, Misa (2007), "An improved upper bound on the queuenumber of the hypercube", Information Processing Letters, 104 (2): 41–44, MR 2343263.
- Heath, Lenwood S.; MR 1172748.
- Heath, Lenwood S.; MR 1181408.
- MR 2920058.
- S2CID 2633083.
- Pai, Kung-Jui; Chang, Jou-Ming; Wang, Yue-Li (2008), "A note on "An improved upper bound on the queuenumber of the hypercube"", Information Processing Letters, 108 (3): 107–109, MR 2452135.
- Rengarajan, S.; Veni Madhavan, C. E. (1995), "Stack and queue number of 2-trees", Computing and Combinatorics: First Annual International Conference, COCOON '95 Xi'an, China, August 24–26, 1995, Proceedings, Lecture Notes in Computer Science, vol. 959, Berlin: Springer, pp. 203–212, MR 1450116.
- Shahrokhi, Farhad; Shi, Weiping (2000), "On crossing sets, disjoint sets, and pagenumber", Journal of Algorithms, 34 (1): 40–53, MR 1732197.
- MR 2046017.
- S2CID 2361133.
- Bibcode:2006math......1293W.
External links
- Stack and Queue Layouts, Problems presented in Summer 2009, Research Experiences for Graduate Students, Douglas B. West