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.
Definition A queue layout of a given graph is defined by a total ordering of the vertices of the graph together with a partition of the edges into a number of "queues". The set of edges in each queue is required to avoid edges that are properly nested: if ab and cd are two edges in the same queue, then it should not be possible to have a < c < d < b in the vertex ordering. The queue number qn(G) of a graph G is the minimum number of queues in a queue layout. Equivalently, from a queue layout, one could process the edges in a single queue using a queue data structure, by considering the vertices in their given ordering, and when reaching a vertex, dequeueing all edges for which it is the second endpoint followed by enqueueing all edges for which it is the first endpoint. 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. Another equivalent definition of queue layouts involves embeddings of the given graph onto a cylinder, with the vertices placed on a line in the cylinder and with each edge wrapping once around the cylinder. Edges that are assigned to the same queue are not allowed to cross each other, but crossings are allowed between edges that belong to different queues. Queue layouts were defined by Heath & Rosenberg (1992), by analogy to previous work on book embeddings of graphs, which can be defined in the same way using stacks in place of queues. 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.
Graph classes with bounded queue number Every tree has queue number 1, with a vertex ordering given by a breadth-first traversal. Pseudoforests and grid graphs also have queue number 1. Outerplanar graphs have queue number at most 2; the 3-sun graph (a triangle with each of its edges replaced by a triangle) is an example of an outerplanar graph whose queue number is exactly 2. Series–parallel graphs have queue number at most 3, while the queue number of planar 3-trees is at most 5. Binary de Bruijn graphs have queue number 2. The d-dimensional hypercube graph has queue number at most d − ⌊ log 2 d ⌋ {\displaystyle d-\lfloor \log _{2}d\rfloor } . The queue numbers of complete graphs Kn and complete bipartite graphs Ka,b are known exactly: they are ⌊ n / 2 ⌋ {\displaystyle \lfloor n/2\rfloor } and min { ⌈ a / 2 ⌉ , ⌈ b / 2 ⌉ } {\displaystyle \min\{\lceil a/2\rceil ,\lceil b/2\rceil \}}
respectively. 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. 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.
Related invariants Graphs with low queue number are sparse graphs: 1-queue graphs with n vertices have at most 2n – 3 edges, and more generally graphs with queue number q have at most 2qn – q(2q + 1) edges. This implies that these graphs also have small chromatic number: in particular 1-queue graphs are 3-colorable, and graphs with queue number q may need at least 2q + 1 and at most 4q colors. In the other direction, a bound on the number of edges implies a much weaker bound on the queue number: graphs with n vertices and m edges have queue number at most O ( m ) {\displaystyle O({\sqrt {m}})} . This bound is close to tight, because for random d-regular graphs the queue number is, with high probability,
Ω ( d n n 1 / d ) . {\displaystyle \Omega \left({\frac {\sqrt {dn}}{n^{1/d}}}\right).}
… excerpt ends here. Continue reading the full article.
