Queue number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
The nesting condition ensures that, when a vertex is reached, all of the edges for which it is the second endpoint are ready to be dequeued.
As they observed, these layouts are also related to earlier work on sorting permutations using systems of parallel queues, and may be motivated by applications in VLSI design and in communications management for distributed algorithms.
[1] Every tree has queue number 1, with a vertex ordering given by a breadth-first traversal.
[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).
[15] This bound is close to tight, because for random d-regular graphs the queue number is, with high probability, Graphs with queue number 1 have book thickness at most 2.
[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.
[21] 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.
[23] More generally, because of their bounded expansion, it is possible to check whether any sentence in the first-order logic of graphs is valid for a given graph of bounded queue number, in linear time.
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.
