Stack and Queue Layouts (1992)

Originator(s): L. Heath et al. (presented by B. Reiniger - REGS 2009)

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). We say that 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 not considered crossing nor nested. A k-stack [k-queue] layout of a graph G is a vertex ordering along with a k-edge-coloring so that in each color class the edges are pairwise non-crossing [non-nested]. The stack number of G, denoted sn(G), is the least k such that G has a k-stack layout. The queue number, denoted qn(G), is the least k such that G has a k-queue layout.

Background: The stack number of a graph was introduced in 1973 by Ollman [O] as the book thickness of a graph; placing the vertices in some order along the spine of a book, the book thickness is the minimum number of pages needed to draw the edges so that edges on the same page do not cross. The seminal paper for the study of book thickness (also called pagenumber) in graph theory is [BK], cited already 27 times.

These layouts model the processing of edges. When following the ordering on the vertices, we prepare edges for processing upon reaching their left endpoint, and we complete processing upon reaching their 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. The edges of a graph G can be processed by k stacks [k queues] if and only if sn(G)≤k [qn(G)≤k]. Stack number is more fully understood than queue number.

Conjecture 1: (Heath et al. [HLR]) Planar graphs have bounded queue number.

Comments: Yannakakis [Y] showed that planar graphs have stack number at most 4, which is sharp. It is unknown even for bipartite planar graphs whether the queue number is bounded, but they have stack number at most 2. A graph has stack number 1 if and only if it is outerplanar, and it has stack number at most 2 if and only if it is a subgraph of a planar Hamiltonian graph.

Question 2: (Ganley and Heath [GH]) What is the largest queue number among k-trees?

Comments: Extremal problems for monotone parameters are of interest in the class of k-trees, because these are the maximal graphs with treewidth k. Ganley and Heath [GH] showed that the stack number of a k-tree is at most k+1 [GH], and this is sharp for k≥3 [VWY]. Dujmovic, Morin, and Wood [DMW] showed that the queue number of a k-tree is bounded by 3^k6^{(4^k-3k-1)/9}-1 (hence graphs with treewidth k satisfy the same bound), but this bound is unlikely to be sharp. The queue number is 1 for a tree and at most 3 for a 2-tree.

Question 3: (Heath et al. [HLR]) Is the stack number or the queue number bounded by a function of the other?

Comments:

If G has m edges, then sn(G)≤72√m and qn(G)≤e√m, where e is the base of the natural logarithm.
[HLR]: If H is a ternary hypercube, the sn(H)∈Ω(3^qn(H)).
[DW05]: If the queue number is bounded by some function of the stack number, then the queue number is bounded by a polynomial function of the stack number.
[DW05]: The queue number is bounded by a function of the stack number if and only if bipartite 3-stack graphs have bounded queue number.

The queue number is not bounded by any function of the maximum degree.

Results on stack numbers and queue numbers for various classes of graphs appear in [DW04], where references to the original results may be found.

References:
[BK] Bernhart, Frank; Kainen, Paul C. The book thickness of a graph. J. Combin. Theory Ser. B 27 (1979), no. 3, 320--331.
[DMW] Dujmovic, Vida; Morin, Pat; Wood, David R. Layout of graphs with bounded tree-width. SIAM J. Comput. 34 (2005), no. 3, 553--579.
[DW04] Dujmovic, Vida; Wood, David R. On linear layouts of graphs. Discrete Math. Theor. Comput. Sci. 6 (2004), no. 2, 339--357.
[DW05] Dujmovic, Vida; Wood, David R. Stacks, queues and tracks: layouts of graph subdivisions. Discrete Math. Theor. Comput. Sci. 7 (2005), no. 1, 155--201.
[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.
[O] L. T. Ollmann, On the book thicknesses of various graphs, in Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, F. Hoffman, R.B. Levow, and R.S.D. Thomas, eds., Congr. Numer. 8 (1973), 459.
[VWY] Vandenbussche, J.; West, D.B.; Yu, G.; The pagenumber of k-trees. SIAM J. Discrete Math. (to appear).
[Y] M. Yannakakis, Embedding planar graphs in four pages, J. Comput. System Sci., 38 (1986), pp. 36--67.