Originator: Ben Reiniger (presented by Ben Reiniger - REGS 2010)
Definitions:
Given a graph G and a linear ordering < on the vertices,
denote the endpoints of an edge e by l(e) and r(e), where
l(e) < r(e). Nonincident edges e and f with
l(e) < l(f) are
crossing if l(e) < l(f) < r(e) < r(f),
nested if l(e) < l(f) < r(f) < r(e).
Incident edges are considered neither crossing nor nested.
A stack is a set of pairwise non-crossing edges.
A queue is a set of pairwise non-nested edge.
A k-queue/stack (or "k-quack") layout of a graph G
is a vertex ordering along with a k-edge-coloring so that each color
class is a stack or a queue. The quack number of G is the
least k such that G has a k-quack layout.
Background: The stack number (the minimum number of stacks in a stack-only layout) was introduced in 1973 by Ollman as the book thickness of a graph; it has also been called the pagenumber. The queue number(the minimum number of queues in a queue-only layout) was introduced in 1992 by Heath et al. These layouts model the processing of edges. When following the ordering on the vertices, we prepare an edge for processing upon reaching its left endpoint, and we complete processing upon reaching its right endpoint. In stacks, the processing is completed in Last-In First-Out fashion; in queues, it is completed in First-In First-Out fashion.
Note that the quack number is bounded above by both the stack number and queue number.
Question 1: When does the quack number equal the minimum of the stack number and the queue number? How much smaller can it be?
Question 2: What are the quack numbers of complete graphs and complete bipartite graphs?
Comments: Heath and Rosenberg [HR] noted that each queue in a layout of an n-vertex graph has at most 2n-3 edges. To see this, note that each edge has a "midpoint" along the vertex ordering, a queue cannot have two edges with the same midpoint, and there are 2n-3 possible midpoints. The same bound holds for stacks since stacks are outerplanar graphs, but in stacks the same n edges are always counted, since the vertex ordering is fixed, so each additional stack contributes at most n-3 new edges. One can also restrict the contribution from queues, since there is only one edge each with the four outermost endpoints, then two each for the next four, and so on, so the number of edges contributed by successive queues must gradually decline. More delicate counting arguments can further improve the lower bound; perhaps the quack number of Kn is also n/2.
For complete bipartite graphs, say Kn,n, the pagenumber is between n/2 and roughly 2n/3 [ENO], and the queue number is ⌈n/2⌉ [HR]. Bipartite outerplanar graphs with m vertices have at most 3m/2-2 edges; if the analogous bound holds for queues in bipartite graphs, then the quack number of Kn,n is at least n/3; is this sharp?
Bounds on stack numbers and queue numbers have been found for many classes of graphs, a few of which are listed below. Further questions and references about these parameters can be found in a 2009 REGS problem.
| Graph | stack # | queue # | source |
|---|---|---|---|
| Kn | ⌈n/2⌉ | ⌊n/2⌋ | [DW] |
| k-trees | ≤k+1 (tight) | ≤3k6(4k-3k-1)/9-1 | [GH], [VWY] |
| Planar graphs | ≤4 (tight) | ??? | [DW] |
| d-cube | d-1(?) [KHT] | ≤d-1 for d=2,3 ≤d-2 for d=4,5,6,7 ≤d-3 for d≥8 ≥⌈d/2⌉ for any d |
[PCW] |
| N-vertex ternary cube |
Ω(N1/9-ε) for any ε>0 |
≤2 log3 N | [HLR] |
References:
[DW] Dujmovic, Vida; Wood, David R. On linear layouts of graphs. Discrete Math.
Theor. Comput. Sci. 6 (2004), no. 2, 339-357.
[ENO] Enomoto, Hikoe; Nakamigawa, Tomoki; Ota, Katsuhiro On the pagenumber of
complete bipartite graphs. J. Combin. Theory Ser. B 71 (1997), no. 1,
111-120.
[GH] Ganley, Joseph L.; Heath, Lenwood S. The pagenumber of k-trees is O(k).
Discrete Appl. Math. 109 (2001), no. 3, 215-221.
[HLR] Heath, Lenwood S.; Leighton, Frank Thomson; Rosenberg, Arnold L.
Comparing queues and stacks as mechanisms for laying out graphs. SIAM J.
Discrete Math. 5 (1992), no. 3, 398-412.
[HR] Heath, Lenwood S.; Rosenberg, Arnold L. Laying out graphs using queues.
SIAM J. Comput. 21 (1992), no. 5, 927-958.
[KHT] Konoe, M., Hagiwara,K. Tokura, N.: On the pagenumber of hypercubes and
cube-connected cycles. IEICE Trans. J71-D(3), 490-500 (1988)
[PCW] Kung-Jui Pai, Jou-Ming Chang, Yue-Li Wang, A new upper bound on the
queuenumber of hypercubes, Discrete Mathematics, Volume 310, Issues 13-14, 28
July 2010, Page 2059,
[VWY] Vandenbussche, J.; West, D.B.; Yu, G.; The pagenumber of k-trees. SIAM J.
Discrete Math. Volume 23, Issue 3, pp. 1455-1464 (2009)