A collection of existing results on stack and queue numbers

Last updated: 2026-02-08

In a total order of the vertices of a graph, two edges with no endpoint in common can be crossing, nested, or disjoint. A k-stack (respectively, k-queue) layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of pairwise non-crossing (respectively, non-nested) edges. Motivated by numerous applications, stack layouts (also called book embeddings) and queue layouts are widely studied in the literature. We survey existing results regarding upper and lower bounds on stack number and queue number of various classes of graphs.

Octahedron graph
The octahedron graph in 2 stacks (left), 2 queues (mid), and 3 tracks (right)
Papers per year
The number of papers on linear layouts since their introduction in 1970s

Stack number

A book embedding is an embedding of a graph to a collection of books, that is, half-planes having the same line as their boundary. The vertices of the graph lie on this boundary line, called the spine, and the edges stay within a single half-plane. The book thickness of a graph (also called page number, stack number and fixed outerthickness) is the smallest possible number of half-planes for any book embedding of the graph. Stack layouts were introduced by Ollmann in 1973.

graph class lower bound reference upper bound reference
tree 1 gen-ref-BK79 1 gen-ref-BK79
outerplanar 1 gen-ref-BK79 1 gen-ref-BK79
series-parallel 2 gen-ref-RM95 2 gen-ref-RM95
planar 3-tree 3 gen-ref-H84 3 gen-ref-H84
Halin 2 gen-ref-G95 2 gen-ref-G95
planar Laman 3 [dot] 4 gen-ref-Y89
planar bipartite 2 [img] 2 gen-ref-FMP95 gen-ref-O98
planar max-degree ≤ 4 2 [img] 2 gen-ref-BGR16 gen-ref-G73
planar 3-connected max-degree ≤ 5 2 [img] 2 gen-ref-HK19
planar max-degree ≤ 5 2 [img] 3 gen-ref-GY19
planar max-degree ≥ 7 3 [dot] [img] 4 gen-ref-Y89
maximal planar max-degree ≤ 6 2 [img] 2 gen-ref-G73
planar 4 [img] gen-ref-BKKPRU20 4 gen-ref-Y89
toroidal (genus 1) 4 [img] gen-ref-BKKPRU20 7 gen-ref-E97
genus g Ω(√g) gen-ref-HI92 O(√g) gen-ref-M94
projective plane (non-orientable genus 1) 4 [img] gen-ref-BKKPRU20 6 gen-ref-ONN19
proper minor-closed Ω(√g) gen-ref-HI92 open gen-ref-B03 gen-ref-ONN19
1-planar 4 gen-ref-ABK15 gen-ref-BKZ15 10 gen-ref-F20 gen-ref-F23
k-planar Ω(√ k) gen-ref-ABK15 gen-ref-BLGGMR20 O(k log n) gen-ref-DF18
outer 1-planar 2 gen-ref-ABBGHNR16 2 gen-ref-ABBGHNR16
outer k-planar 1.5k + 3 gen-ref-FGKOW24 gen-ref-GH01
pathwidth k k gen-ref-TY02 k gen-ref-TY02
treewidth k k + 1 gen-ref-VDG09 k + 1 gen-ref-GH01
complete Kn ⌈n / 2⌉ gen-ref-BK79 ⌈n / 2⌉ gen-ref-BK79
complete bipartite Kn,m min(n, m) gen-ref-BK79 gen-ref-SPE13 min(n, m) gen-ref-BK79 gen-ref-ENO97

Queue number

In a queue layout, the vertices of a graph are restricted to a line and the edges are drawn at different half-planes delimited by this line, called queues. The task is to find a linear order of the vertices along the underlying line and a corresponding assignment of the edges of the graph to the queues, so that no two independent edges of the same queues are nested. The queue number of a graph is the smallest number of queues that are required by any queue layout of the graph. Queue layouts were defined by Heath and Rosenberg in 1992.

graph class lower bound reference upper bound reference
tree 1 gen-ref-HR92 1 gen-ref-HR92
outerplanar 2 gen-ref-HR92 2 gen-ref-HLR92
outerplanar bipartite 1 gen-ref-BDDEW18 1 gen-ref-BDDEW18
series-parallel 3 gen-ref-W17 3 gen-ref-RM95
planar 3-tree 4 gen-ref-ABGKP18 5 gen-ref-ABGKP18
Halin 2 gen-ref-G95 2 gen-ref-BDDEW18
X-Tree 2 gen-ref-HR92 2 gen-ref-HR92
planar bipartite 3 gen-ref-FKMPR23 28 gen-ref-FKMPR23
planar max-degree Δ=3 2 [img] O(Δ2) gen-ref-BFGMMRU19 gen-ref-DMW19
planar 4 gen-ref-ABGKP18 42 gen-ref-DJMMUW19 gen-ref-BGR23
genus g 4 gen-ref-ABGKP18 O(g) gen-ref-DJMMUW19
proper minor-closed 4 gen-ref-ABGKP18 O(1) gen-ref-DJMMUW19
1-planar 4 gen-ref-ABGKP18 82 gen-ref-DMW20 gen-ref-BDHK22
k-planar Ω(√ k) gen-ref-ABGKP18 O(f(k)) gen-ref-DJMMUW19 gen-ref-DMW20
outer 1-planar 3 gen-ref-ABBGHNR16 3 gen-ref-ABBGHNR16
outer k-planar 21.5k+2 - 1 gen-ref-FGKOW24 gen-ref-W17
pathwidth k k gen-ref-W02 k gen-ref-W02
treewidth k k + 1 gen-ref-W17 2k - 1 gen-ref-W17
hypercube Qn (n-2)/3 gen-ref-GSV12 n - ⌊log(n)⌋ gen-ref-HR92 gen-ref-PCW10 gen-ref-GSV12
folded hypercube FQn (n-2)/3 gen-ref-GSV12 n gen-ref-GHY25 gen-ref-Pai26
complete Kn ⌊n / 2⌋ gen-ref-HR92 ⌊n / 2⌋ gen-ref-HR92
complete bipartite Kn,m min(⌈n / 2⌉, ⌈m / 2⌉) gen-ref-HR92 min(⌈n / 2⌉, ⌈m / 2⌉) gen-ref-HR92

Track layouts

Track layouts are closely related to queue layouts; they were introduced by Dujmović et al., although similar structures are implicit in several previous works studying low-volume three-dimensional graph drawings. A track layout of a graph is a partition of its vertices into sequences, called tracks, such that the vertices in each sequence form an independent set and the edges between each two pairs of tracks form a non-crossing set.

The track number is exactly determined for several basic classes. Trees have track number 3 (gen-ref-FLW06). Outerplanar graphs have track number 5 (see [img] and gen-ref-DPW04). Outerplanar bipartite graphs have track number 3 (see [img], gen-ref-FLW06, gen-ref-BDDEW18). For Halin graphs, the track number is between 5 and 6 (lower bound witnessed by [img]; upper bound in gen-ref-BDDEW18). For X-trees, the track number is exactly 5 (see [img] and gen-ref-P19).

For more complex planar families, current bounds are as follows. Series-parallel graphs have track number at least 7 (gen-ref-DMW05, gen-ref-M20) and at most 15 (gen-ref-GLM03). Planar 3-trees have track number between 8 and 25 (gen-ref-P19). Planar graphs have track number between 8 and 225 (gen-ref-P19). Planar bipartite graphs have track number at least 5 (witnessed by [dot]) and at most 225 (gen-ref-P19). For graphs of treewidth k, the track number is at least 1 ⁄ 2 (k + 1)(k + 2) + 1 (gen-ref-DMW05, gen-ref-M20) and at most (k + 1)(2k+1-2)k (gen-ref-W17).

Mixed layouts

Stack and queue layouts are generalized in mixed linear layouts in which every edge is assigned to a stack or to a queue that is defined with respect to a common vertex order (gen-ref-HR92). Such a layout is called an s-stack q-queue layout, or an (s,q)-layout , if it utilizes s stacks and q queues. One reason for studying mixed layouts is that they model the dequeue data structure, as a dequeue may be simulated by two stacks and one queue (gen-ref-DW05, gen-ref-A14).

Heath and Rosenberg gen-ref-HR92 suggested to study mixed linear layouts back in 1992; specifically they conjectured that every planar graph admits a mixed 1-stack 1-queue layout. gen-ref-DW05, gen-ref-EM14, and gen-ref-Miy20 investigate mixed layouts of graph subdivisions. In particular, gen-ref-DW05 shows that four division vertices per edge of a planar graph are sufficient to construct a mixed 1-stack 1-queue. The bound has been improved to one division vertex per edge in gen-ref-P17. In the same work, the conjecture has been disproved by presenting a planar graph (of treewidth 3) that does not admit a (1,1)-layout. Subsequently, other papers have followed strengthening the result by showing that not even series-parallel (gen-ref-ABKM22) or planar bipartite graphs (gen-ref-FKMPR23) admit a mixed 1-stack 1-queue layout.

Formally, the mixed page number is introduced in gen-ref-ABGKP22, who study layouts of complete and complete bipartite graphs. Further investigations include computational hardness results (gen-ref-CKN19), who show that testing the existence of a 2-stack 1-queue layout is NP-complete. gen-ref-Deb23 study mixed layouts of directed acyclic graphs. Very recently, gen-ref-KKPU25 and gen-ref-HMP25 related the queue, stack, and mixed page number to each other.

Stacks vs Queues

Some of the most important open problems for linear layouts of graphs concern the relationship between stack number and queue number. For example, every 1-stack graph admits a 2-queue layout, and every 1-queue graph admits a 2-stack layout (gen-ref-HLR92). Already in 1992, Heath, Leighton, and Rosenberg (gen-ref-HLR92) asked whether the queue number of a graph is bounded as a function of its stack number, and symmetrically whether the stack number is bounded in terms of the queue number. This question is often phrased as asking whether stacks can be “transformed into” queues. Dujmović and Wood (gen-ref-DW05) showed that bounding the queue number by the stack number is equivalent to asking whether bipartite graphs with stack number three have bounded queue number, thereby identifying a very restricted setting in which the problem remains open.

Partial results show an asymmetry between the two parameters. Dujmović, Eppstein, Hickingbotham, Morin, and Wood (gen-ref-DEHMW22) proved that the stack number is not bounded by the queue number by constructing graphs with queue number at most four and unbounded stack number. An alternative proof of this result is given in gen-ref-HS23. Stronger separations are known: Leung (gen-ref-Leu23) constructed graphs with queue number three and unbounded stack number, and unbounded stack number also arises in several graph product constructions, including three-dimensional grid-like products (gen-ref-EHNMSW24).

In contrast, no such separation is known in the other direction, and whether the queue number is bounded by the stack number remains open. Recently, Alam et al. (gen-ref-ABGKP22) asked whether the queue number is bounded by the mixed number, and Katheder et al. (gen-ref-KKPU25) showed that this question is equivalent to the original stack-versus-queue problem. Thus, despite substantial progress on separations and special cases, the central open problem remains: determine whether there exists a function f such that qn(G) ≤ f(sn(G)) for all graphs.

For directed acyclic graphs and posets, the relationship has been studied in more detail. Heath and Pemmaraju (gen-ref-HP99, gen-ref-HPT99) relate stack and queue layouts of DAGs and derive bounds for special classes, while earlier work on posets (gen-ref-HP97) establishes several parameterized bounds.

Directed graphs

Stack and queue layouts can be extended to directed acyclic graphs (DAGs) by requiring that the vertex order is a topological order of the DAG. It was first discussed by Heath et al. Similar layouts are studied for posets (partially ordered sets), or equivalently, DAGs without transitive edges.

For stack layouts of DAGs, gen-ref-HPT99 and gen-ref-HP99 show that directed trees and unicyclic DAGs have stack numbers 1 and 2, respectively; gen-ref-MS09 proves that N-free upward planar DAGs, which contain series-parallel digraphs, have stack number 2. gen-ref-AL05 investigate stack layouts of bipartite and complete multipartite ordered sets. A study in gen-ref-FFR13 gave several conditions under which upward planar triangulations have a constant stack number: (i) maximal upward planar 3-trees and (ii) planar triangulations with a bounded (directed) diameter. Later gen-ref-NP21 and gen-ref-BLMN22 extend the classes of DAGs that have bounded stack number. A sub-linear bound on the stack number of upward planar graphs is known (gen-ref-JMU22a) and a (very large) constant upper bound on the stack number of (non-upward) outerplanar DAGs (gen-ref-JMU22b gen-ref-ABGK25). For the lower bounds, there exist upward outerplanar DAGs with stack number 4, upward planar 3-tree DAGs and planar posets with stack number 5 (gen-ref-NP21, gen-ref-JMU22a), and (non-upward) 2-tree DAGs with unbounded stack number (gen-ref-JMU22b).

Queue layouts of DAGs have been first studied by Heath and Pemmaraju (gen-ref-HP99, gen-ref-HPT99). They characterize 1-queue DAGs as the ones admitting arched leveled-planar layouts, show that every unicyclic DAG has a 2-queue layout, and consider the computational complexity of recognizing 1-queue DAGs (linear time) and 4-queue DAGs (NP-complete). It is easy to verify that the queue number of directed acyclic 2-trees is unbounded (img). Subsequent works focus on the queue number of posets. gen-ref-HP97 derives upper bounds in terms of its jumpnumber, length, and width; it also shows an Ω(√n) lower bound for the class of n-element planar posets. Notably, gen-ref-HP97 observes that a width-w poset has queue number at most w2, while planar width-w posets have queue number at most 4w. gen-ref-KMU18 improves the upper bound for planar posets to 3w-2 and for general posets to w2-w+1. Later gen-ref-ABGKP23 reduced the upper bound for general posets to (w-1)2+1 and the lower bound to w+1, thus refuting the conjecture of Heath and Pemmaraju that width-w posets always have queue number w. The conjecture has also been refuted for 2-dimensional posets (gen-ref-Pup22) and a width-w posets with w2/8 queue number has been presented (gen-ref-FUW21).
By analogy with undirected graphs, track numbers of DAGs can be defined and studied; gen-ref-DW06 and gen-ref-GLMW09 provide several results for track numbers with low-volume three-dimensional upward drawings.

Extensions

Besides traditional stack/queue layouts, a number of extended variants of linear layouts have been studied.

Dispersable layouts. Dispersable (a.k.a. matching) book embeddings strengthen stack layouts by requiring that each page induces a matching. Alam et al. formalize and study dispersable book thickness, disprove the Bernhart–Kainen conjecture (gen-ref-BK79) already for 3-regular and 4-regular bipartite graphs, and give positive results for restricted planar bipartite graphs (gen-ref-ABDGKP21).

Forest stack number. A further restriction is to require each stack/page to induce a forest (interpolating between ordinary stack layouts and matching stack layouts). This variant is explored in the thesis “Forest Stack Layouts” (gen-ref-Sch22). An intriguing (unconfirmed) conjecture is that every graph with stack number s admits a forest stack layout on (s+1) pages.

Local stack/queue numbers. Local variants bound how many stacks/queues each edge participates in, rather than bounding the total number of pages. Merker and Ueckerdt study the local variants and show strong bounds for graphs of bounded treewidth (gen-ref-MU19 gen-ref-MU20). A complementary direction is developed for complete graphs in gen-ref-FMUV21, which studies several linear-layout parameters on complete graphs in a unified way.

Rique layouts and Priority queues. Beyond stacks and queues, one can impose ordering constraints induced by other data structures. Rique layouts model a richer data structure and induce the rique-number. Bekos et al. initiate the study, including characterizations for 1-page cases and bounds for complete graphs (gen-ref-BFKKKR22). Subsequent work studies the deque/rique numbers for complete and complete bipartite graphs (gen-ref-BKPR23) and investigates the rique-number on structured classes such as series-parallel graphs and planar bipartite graphs (gen-ref-AR25). Mixed stack/queue/rique layouts of planar graphs are studied in gen-ref-KP24. Di Giacomo et al. study linear layouts where edges are assigned to pages subject to priority-queue constraints (gen-ref-DDFUZ25).

Defective linear layouts. Defective variants allow a controlled number of forbidden configurations per page (analogous in spirit to defective colorings). Bekos et al. introduce and study defective linear layouts in gen-ref-BBGD0PTW25.

References

  1. A SAT-based solver for constructing optimal linear layouts of graphs.
  2. K. J. Pai. An improved upper bound on the queue number of the folded hypercube. Discrete Applied Mathematics, 381:232–236, 2026.
  3. D. Haun, L. Merker, S. Pupyrev. Forbidden patterns in mixed linear layouts. STACS, 45:1–45:21, 2025.
  4. J. Katheder, M. Kaufmann, S. Pupyrev, and T. Ueckerdt. Transforming stacks into queues: Mixed and separated layouts of graphs. STACS, LIPIcs 327, 56:1–56:18, 2025.
  5. J. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann. The page number of monotone directed acyclic outerplanar graphs is four or five. Graph Drawing and Network Visualization (GD), pp 9:1–9:17, 2025.
  6. M. A. Bekos, C. Binucci, E. Di Giacomo, W. Didimo, L. Grilli, M. E. Pavlidi, A. Tappini, and A. Weinberger. Defective linear layouts of graphs (Poster Abstract). Graph Drawing and Network Visualization (GD), 49:1–49:4, 2025.
  7. E. Di Giacomo, W. Didimo, H. Förster, T. Ueckerdt, J. Zink. Linear layouts of graphs with priority queues. WADS, 29:1-29:17, 2025.
  8. S. R. Azgor, Md. S. Rahman. On the rique number of series-parallel graphs and planar bipartite graphs. ICAA, pp 3-14, 2025
  9. X. Geng, Y. Hao, and X. Yang. Queue layouts on folded hypercubes. Discrete Applied Mathematics, 373:119–126, 2025.
  10. O. Firman, G. Gutowski, M. Kryven, Y. Okada, and A. Wolff. Bounding the treewidth of outer k-planar graphs via triangulations. International Symposium on Graph Drawing, pp 1-17, 2024.
  11. D. Eppstein, R. Hickingbotham, L. Merker, S. Norin, M. T. Seweryn, and D. R. Wood. Three-dimensional graph products with unbounded stack-number. Discrete & Computational Geometry, 71(4):1210–1237, 2024.
  12. M. Kaufmann, M. E. Pavlidi. A note on mixed linear layouts of planar graphs. EuroCG, 2024.
  13. M. A. Bekos, M. Kaufmann, M. E. Pavlidi, and X. Rieger. On the deque and rique numbers of complete and complete bipartite graphs. CCCG, pp 89-95, 2023.
  14. M. A. Bekos, M. Gronemann, C. Raftopoulou. An improved upper bound on the queue number of planar graphs. Algorithmica, 85(2):544-562, 2023.
  15. H. Förster, M. Kaufmann, L. Merker, S. Pupyrev, C. Raftopoulou. Linear layouts of bipartite planar graphs. Algorithms and Data Structures Symposium (WADS), pp 444-459, 2023.
  16. F. Brandenburg. Embedding 1-planar graphs in ten pages. arXiv preprint arXiv:2312.15786, 2023.
  17. J. Alam, M. Bekos, M. Gronemann, M. Kaufmann, S. Pupyrev. Lazy queue layouts of posets. Algorithmica 85(5):1176-1201, 2023.
  18. D. Haun. Mixed page number of planar directed acyclic graphs. BSs thesis, Karlsruhe Institute of Technology, 2023.
  19. Y. H. A. Leung. Graphs with queue number three and unbounded stack number. arXiv preprint arXiv:2303.15660, 2023.
  20. P. Hliněný and A. Straka. Stack and queue numbers of graphs revisited. EUROCOMB, pp 601–606, 2023.
  21. M. A. Bekos, S. Felsner, P. Kindermann, S. G. Kobourov, J. Kratochvíl, and I. Rutter. The rique-number of graphs. Graph Drawing and Network Visualization (GD), pp 371-386, 2022.
  22. L. Scherzer. Forest Stack Layouts. Bachelor’s thesis, Karlsruhe Institute of Technology, 2022.
  23. V. Dujmović, D. Eppstein, R. Hickingbotham, P. Morin, and D. R. Wood. Stack-number is not bounded by queue-number. Combinatorica, 42(2):151–164, 2022.
  24. P. Jungeblut, L. Merker, and T. Ueckerdt. Directed acyclic outerplanar graphs have constant stack number. Symposium on Foundations of Computer Science, pp 1937-1952, 2023.
  25. S. Pupyrev. Queue layouts of two-dimensional posets. International Symposium on Graph Drawing, pp 353-360, 2022.
  26. P. Jungeblut, L. Merker, and T. Ueckerdt. A sublinear bound on the page number of upward planar graphs. Symposium on Discrete Algorithms, pp 963-978, 2022.
  27. S. Bhore, G. Da Lozzo, F. Montecchiani, and M. Nöllenburg. On the upward book thickness problem: combinatorial and complexity results. European Journal of Combinatorics, 2022.
  28. M. A. Bekos, G. Da Lozzo, P. Hliněný, M. Kaufmann. Graph product structure for h-framed graphs. International Symposium on Algorithms and Computation, 2022.
  29. J. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann and S. Pupyrev. The mixed page number of graphs. Theoretical Computer Science, 2022.
  30. P. Angelini, M.A. Bekos, P. Kindermann, T. Mchedlidze. On mixed linear layouts of series-parallel graphs. Theoretical Computer Science, pp 129–138, 2022.
  31. M. J. Alam, M. A. Bekos, V. Dujmović, M. Gronemann, M. Kaufmann, and S. Pupyrev. On dispersable book embeddings. Theoretical Computer Science, 861:1–22, 2021.
  32. M. Nöllenburg and S. Pupyrev. On families of planar DAGs with constant stack number. International Symposium on Graph Drawing, pp 135-151, 2023.
  33. S. Felsner, T. Ueckerdt, and K. Wille. On the queue-number of partial orders. International Symposium on Graph Drawing, pp 231-241, 2021.
  34. S. Felsner, L. Merker, T. Ueckerdt, P. Valtr. Linear layouts of complete graphs. International Symposium on Graph Drawing, pp 257-270, 2021.
  35. L. Merker and T. Ueckerdt. The local queue number of graphs with bounded treewidth. Graph Drawing and Network Visualization (GD), pp 26–39, 2020.
  36. L. Merker. Ordered covering numbers. Diss. Karlsruhe Institute of Technology, 2020.
  37. F. Brandenburg. Book embeddings of k-map graphs. arXiv preprint arXiv:2012.06874, 2020.
  38. M. A. Bekos, G. D. Lozzo, S. Griesbach, M. Gronemann, F. Montecchiani, and C. Raftopoulou. Book embeddings of nonplanar graphs with small faces in few pages. Symposium on Computational Geometry, pp 1-17, 2020.
  39. M. A. Bekos, M. Kaufmann, and F. Klute, S. Pupyrev, C. Raftopoulou, and T. Ueckerdt. Four pages are indeed necessary for planar graphs. Journal of Computational Geometry, pp 332-353, 2020.
  40. M. Miyauchi. Topological stack-queue mixed layouts of graphs. Transactions on Fundamentals of Electronics, Communications and Computer Sciences, pp 510-522, 2020.
  41. L. Merker and T. Ueckerdt. Local and union page numbers. Graph Drawing and Network Visualization (GD), pp 447–459, 2019.
  42. S. Pupyrev. Improved bounds for track numbers of planar graphs. Journal of Graph Algorithms and Applications, pp 323-341, 2020.
  43. V. Dujmović, P. Morin, and D. Wood. Graph product structure for non-minor-closed classes. Journal of Combinatorial Theory, Series B, 162:34-67, 2023.
  44. M. Hoffmann and B. Klemz. Triconnected planar graphs of maximum degree five are subhamiltonian. European Symposium on Algorithms (ESA), pp 58, 2019.
  45. P. de Col, F. Klute and M. N{\"o}llenburg. Mixed linear layouts: Complexity, heuristics, and experiments. Graph Drawing and Network Visualization, pp 460-467, 2019.
  46. X. Guan and W. Yang. Embedding planar 5-graphs in three pages. Discrete Applied Mathematics, pp 108-121, 2019.
  47. V. Dujmović, G. Joret, P. Micek, P. Morin, T. Ueckerdt, D. R. Wood. Planar graphs have bounded queue-number. Symposium on Foundations of Computer Science, pp 862-875, 2019
  48. V. Dujmović, P. Morin, D. R. Wood. Queue layouts of graphs with bounded degree and bounded genus. arXiv preprint arXiv:1901.05594, 2019.
  49. M. Bekos, H. Förster, M. Gronemann, T. Mchedlidze, F. Montecchiani, C. Raftopoulou, T. Ueckerdt. Planar graphs of bounded degree have bounded queue number. Symposium on Theory of Computing, pp 176-184, 2019.
  50. K. Ozeki, A. Nakamoto, T. Nozawa. Book embedding of graphs on the projective plane. SIAM Journal on Discrete Mathematics, pp 1801-1836, 2019.
  51. K. Knauer, and P. Micek and T. Ueckerdt. The queue-number of posets of bounded width or height. International Symposium on Graph Drawing, pp 200-212, 2018.
  52. V. Dujmović and F. Frati. Stack and queue layouts via layered separators. Journal of Graph Algorithms and Applications, pp 89-99, 2018.
  53. J. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, and S. Pupyrev. Queue layouts of planar 3-trees. Algorithmica, pp 1-22, 2020.
  54. M. J. Bannister, W. E. Devanny, V. Dujmović, D. Eppstein, D. R. Wood. Track layouts, layered path decompositions, and leveled planarity. Algorithmica, pp 1-23, 2018.
  55. S. Pupyrev. Mixed linear layouts of planar graphs. Graph Drawing, pp 197-209, 2017.
  56. V. Wiechert. On the queue-number of graphs with bounded tree-width. Electr. J. Comb. 24(1), P1.65, 2017.
  57. M. A. Bekos, M. Gronemann, and C. N. Raftopoulou. Two-page book embeddings of 4-planar graphs. Algorithmica, 75(1):158-185, 2016.
  58. C. Auer, C. Bachmaier, F. J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, and J. Reislhuber. Outer 1-planar graphs. Algorithmica, 74(4):1293-1320, 2016.
  59. M. Alam, F. J. Brandenburg, and S. G. Kobourov. On the book thickness of 1-planar graphs. arXiv preprint arXiv:1510.05891, 2015.
  60. V. Dujmović. Graph layouts via layered separators. Journal of Combinatorial Theory, Series B, 110:79-89, 2015.
  61. M. A. Bekos, M. Kaufmann, and C. Zielke. The book embedding problem from a SAT-solving perspective. International Symposium on Graph Drawing, pp 125-138, 2015.
  62. H. Enomoto and M. Miyauchi. Stack-queue mixed layouts of graph subdivisions. Forum on Information Technology, pages 47-56, 2014.
  63. C. Auer. Planar graphs and their duals on cylinder surfaces. PhD thesis, Universität Passau, 2014.
  64. F. Frati, R. Fulek, A.J. Ruiz-Vargas. On the page number of upward planar directed acyclic graphs. Journal of Graph Algorithms and Applications, 17(3):221–244, 2013.
  65. K. Sperfeld. On the page number of complete odd-partite graphs. Discrete Mathematics, 313(17):1689–1696, 2013.
  66. P. Gregor, R. Škrekovski, and V. Vukašinović. Queue Layouts of Hypercubes. SIAM Journal on Discrete Mathematics, 26(1):77–88, 2012.
  67. Kung-Jui Pai, Jou-Ming Chang, and Yue-Li Wang. A new upper bound on the queuenumber of hypercubes. Discrete Mathematics, 310(4):935–939, 2010.
  68. J. Vandenbussche, W. B. Douglas and Y. Gexin. On the pagenumber of k-trees. SIAM Journal on Discrete Mathematics 23.3: 1455-1464, 2009.
  69. E. Di Giacomo, and G. Liotta, H. Meijer, and S. Wismath. Volume requirements of 3D upward drawings. Discrete Mathematics 309(7): 1824-1837, 2009.
  70. T. Mchedlidze and A. Symvonis. Crossing-free acyclic Hamiltonian path completion for planar st-digraphs. Algorithms and Computation, pp 882-891, 2009.
  71. S. Felsner, G. Liotta, and S. Wismath. Straight-line drawings on restricted integer grids in two and three dimensions. Graph Algorithms and Applications 4, 4:363-398, 2006.
  72. V. Dujmović and D. R. Wood. Upward three-dimensional grid drawings of graphs. Order 23(1): 1-20, 2006.
  73. V. Dujmović, P. Morin, and D. R. Wood. Layout of graphs with bounded tree-width. SIAM Journal on Computing 34.3: 553-579, 2005.
  74. V. Dujmović and D. R. Wood. Stacks, queues and tracks: Layouts of graph subdivisions. Discrete Mathematics and Theoretical Computer Science 7: 155-202, 2005.
  75. M. Alhashem. The book embeddings of ordered sets. MSc thesis, University of Ottawa, 2005.
  76. V. Dujmović, A. Pór, and D. R. Wood. Track layouts of graphs. Discrete Mathematics & Theoretical Computer Science, 6(2):497-522, 2004.
  77. V. Dujmović and D. R. Wood. On linear layouts of graphs. Discrete Mathematics & Theoretical Computer Science, 6(2):339-358, 2004.
  78. R. Blankenship. Book embeddings of graphs. PhD thesis, Louisiana State University, 2003.
  79. E. Di Giacomo and H. Meijer. Track drawings of graphs with constant queue number. In International Symposium on Graph Drawing, pages 214-225. Springer, 2003.
  80. E. Di Giacomo, G. Liotta, and H. Meijer. 3D straight-line drawings of k-trees. Technical report, 2003-473, School of Computing, Queens's University, Kingston, Canada, 2003.
  81. D. Wood. Queue layouts, tree-width, and three-dimensional graph drawing. In Foundations of Software Technology and Theoretical Computer Science, pages 348-359, Springer, 2002.
  82. M. Togasaki and K. Yamazaki. Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs. Discrete Mathematics, 259(1-3):361-368, Elsevier, 2002.
  83. J. L. Ganley and L. S. Heath. The pagenumber of k-trees is O(k). Discrete Applied Mathematics, 109(3):215-221, 2001.
  84. L. S. Heath, S. V. Pemmaraju, and A. N. Trenk. Stack and queue layouts of directed acyclic graphs: Part I. SIAM Journal on Computing, 28(4):1510-1539, 1999.
  85. L. S. Heath and S. V. Pemmaraju. Stack and queue layouts of directed acyclic graphs: Part II. SIAM Journal on Computing, 28(5):1588-1626, 1999.
  86. S. B. Overbay. Generalized book embeddings. PhD thesis, Colorado State University, 1998.
  87. T. Endo. The pagenumber of toroidal graphs is at most seven. Discrete Mathematics, pages 175(1-3):87-96, 1997.
  88. H. Enomoto, T. Nakamigawa, and K. Ota. On the pagenumber of complete bipartite graphs. Journal of Combinatorial Theory, Series B, pages 71(1):111-120. Elsevier, 1997.
  89. L. S. Heath, S. V. Pemmaraju. Stack and queue layouts of posets. SIAM Journal on Discrete Mathematics, 10(4):599-625, 1997.
  90. J. L. Ganley. Stack and queue layouts of Halin graphs. manuscript, 1995.
  91. H. De Fraysseix, P. O. De Mendez, and J. Pach. A left-first search algorithm for planar graphs. Discrete & Computational Geometry, 13(3-4):459-468, 1995.
  92. S. Rengarajan and C. V. Madhavan. Stack and queue number of 2-trees. In International Computing and Combinatorics Conference, pages 203-212. Springer, 1995.
  93. S. M. Malitz. Genus g graphs have pagenumber O(√g). Journal of Algorithms, 17(1):85-109, 1994.
  94. L. S. Heath and S. Istrail. The pagenumber of genus g graphs is O(g). Journal of the ACM , 39(3):479-501, 1992.
  95. L. S. Heath, F. T. Leighton, and A. L. Rosenberg. Comparing queues and stacks as machines for laying out graphs. SIAM Journal on Discrete Mathematics, 5(3):398-412, 1992.
  96. L. S. Heath and A. L. Rosenberg. Laying out graphs using queues. SIAM Journal on Computing, 21(5):927-958, 1992.
  97. M. Yannakakis. Embedding planar graphs in four pages. Journal of Computer and System Sciences, 38(1):36-67, 1989.
  98. L. Heath. Embedding planar graphs in seven pages. In 25th Annual Symposium on Foundations of Computer Science, pages 74-83. IEEE, 1984.
  99. F. Bernhart and P. C. Kainen. The book thickness of a graph. Journal of Combinatorial Theory, Series B, 27(3):320-331, 1979.
  100. G. Ewald. Hamiltonian circuits in simplicial complexes. Geometriae Dedicata 2.1: 115-125, 1973.
  101. L. T. Ollmann. On the book thicknesses of various graphs. In 4th Southeastern Conference on Combinatorics. Graph Theory and Computing, vol. VIII of Congressus Numerantium, p. 459, 1973.
Please cite this page with
@misc{llsurvey,
  author       = {Pupyrev, Sergey},
  title        = {A collection of existing results on stack and queue numbers},
  howpublished = {\url{https://spupyrev.github.io/linearlayouts.html}},
  year         = {2020},
  note         = {Accessed: 2025-01-01}
}