Overview

Last updated: 2024-11-15
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, queue number and track number of various classes of graphs.

The octahedron graph drawn in 2 stacks (left), 2 queues (center), and 3 tracks (right)

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 O(√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 O(√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
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
pathwidth k k gen-ref-W02 k gen-ref-W02
treewidth k k + 1 gen-ref-W17 2k - 1 gen-ref-W17
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 number

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. Track layouts were introduced by Dujmović et al., although similar structures are implicit in several previous works studying low-volume three-dimensional graph drawings.

graph class lower bound reference upper bound reference
tree 3 gen-ref-FLW06 3 gen-ref-FLW06
outerplanar 5 [img] 5 gen-ref-DPW04
outerplanar bipartite 3 [img] 3 gen-ref-FLW06 gen-ref-BDDEW18
series-parallel 7 gen-ref-DMW05 gen-ref-M20 15 gen-ref-GLM03
planar 3-tree 8 gen-ref-P19 25 gen-ref-P19
Halin 5 [img] 6 gen-ref-BDDEW18
X-Tree 5 [img] 5 gen-ref-P19
planar bipartite 5 [dot] 225 gen-ref-P19
planar 8 gen-ref-P19 225 gen-ref-P19
treewidth k 1 ⁄ 2 (k + 1)(k + 2) + 1 gen-ref-DMW05 gen-ref-M20 (k + 1)(2k+1-2)k gen-ref-W17

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). 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.

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-KKPU24 related the queue, stack, and mixed page number to each other.

References

  1. An online solver for stack and queue numbers of graphs.
  2. J. Katheder, M. Kaufmann and S. Pupyrev, and T. Ueckerdt. Transforming stacks into queues: Mixed and separated layouts of graphs. arXiv preprint arXiv:2409.17776, 2024.
  3. M. A. Bekos, M. Gronemann, C. Raftopoulou. An improved upper bound on the queue number of planar graphs. Algorithmica, 85(2):544-562, 2023.
  4. 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.
  5. F. Brandenburg. Embedding 1-planar graphs in ten pages. arXiv preprint arXiv:2312.15786, 2023.
  6. J. Alam, M. Bekos, M. Gronemann, M. Kaufmann, S. Pupyrev. Lazy queue layouts of posets. Algorithmica 85(5):1176-1201, 2023.
  7. D. Haun. Mixed page number of planar directed acyclic graphs. BSs thesis, Karlsruhe Institute of Technology, 2023.
  8. 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.
  9. S. Pupyrev. Queue layouts of two-dimensional posets. International Symposium on Graph Drawing, pp 353-360, 2022.
  10. 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.
  11. 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.
  12. 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.
  13. J. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann and S. Pupyrev. The mixed page number of graphs. Theoretical Computer Science, 2022.
  14. P. Angelini, M.A. Bekos, P. Kindermann, T. Mchedlidze. On mixed linear layouts of series-parallel graphs. Theoretical Computer Science, pp 129–138, 2022.
  15. M. Nöllenburg and S. Pupyrev. On families of planar DAGs with constant stack number. International Symposium on Graph Drawing, pp 135-151, 2023.
  16. S. Felsner, T. Ueckerdt, and K. Wille. On the queue-number of partial orders. International Symposium on Graph Drawing, pp 231-241, 2021.
  17. L. Merker. Ordered covering numbers. Diss. Karlsruhe Institute of Technology, 2020.
  18. F. Brandenburg. Book embeddings of k-map graphs. arXiv preprint arXiv:2012.06874, 2020.
  19. 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.
  20. 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.
  21. M. Miyauchi. Topological stack-queue mixed layouts of graphs. Transactions on Fundamentals of Electronics, Communications and Computer Sciences, pp 510-522, 2020.
  22. S. Pupyrev. Improved bounds for track numbers of planar graphs. Journal of Graph Algorithms and Applications, pp 323-341, 2020.
  23. 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.
  24. M. Hoffmann and B. Klemz. Triconnected planar graphs of maximum degree five are subhamiltonian. European Symposium on Algorithms (ESA), pp 58, 2019.
  25. 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.
  26. X. Guan and W. Yang. Embedding planar 5-graphs in three pages. Discrete Applied Mathematics, pp 108-121, 2019.
  27. 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
  28. V. Dujmović, P. Morin, D. R. Wood. Queue layouts of graphs with bounded degree and bounded genus. arXiv preprint arXiv:1901.05594, 2019.
  29. 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.
  30. K. Ozeki, A. Nakamoto, T. Nozawa. Book embedding of graphs on the projective plane. SIAM Journal on Discrete Mathematics, pp 1801-1836, 2019.
  31. 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.
  32. V. Dujmović and F. Frati. Stack and queue layouts via layered separators. Journal of Graph Algorithms and Applications, pp 89-99, 2018.
  33. J. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, and S. Pupyrev. Queue layouts of planar 3-trees. Algorithmica, pp 1-22, 2020.
  34. 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.
  35. S. Pupyrev. Mixed linear layouts of planar graphs. Graph Drawing, pp 197-209, 2017.
  36. V. Wiechert. On the queue-number of graphs with bounded tree-width. Electr. J. Comb. 24(1), P1.65, 2017.
  37. M. A. Bekos, M. Gronemann, and C. N. Raftopoulou. Two-page book embeddings of 4-planar graphs. Algorithmica, 75(1):158-185, 2016.
  38. M. Alam, F. J. Brandenburg, and S. G. Kobourov. On the book thickness of 1-planar graphs. arXiv preprint arXiv:1510.05891, 2015.
  39. V. Dujmović. Graph layouts via layered separators. Journal of Combinatorial Theory, Series B, 110:79-89, 2015.
  40. 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.
  41. H. Enomoto and M. Miyauchi. Stack-queue mixed layouts of graph subdivisions. Forum on Information Technology, pages 47-56, 2014.
  42. C. Auer. Planar graphs and their duals on cylinder surfaces. PhD thesis, Universität Passau, 2014.
  43. 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.
  44. K. Sperfeld. On the page number of complete odd-partite graphs. Discrete Mathematics, 313(17):1689–1996, 2013.
  45. J. Vandenbussche, W. B. Douglas and Y. Gexin. On the pagenumber of k-trees. SIAM Journal on Discrete Mathematics 23.3: 1455-1464, 2009.
  46. E. Di Giacomo, and G. Liotta, H. Meijer, and S. Wismath. Volume requirements of 3D upward drawings. Discrete Mathematics 309(7): 1824-1837, 2009.
  47. T. Mchedlidze and A. Symvonis. Crossing-free acyclic Hamiltonian path completion for planar st-digraphs. Algorithms and Computation, pp 882-891, 2009.
  48. S. Felsmer, 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.
  49. V. Dujmović and D. R. Wood. Upward three-dimensional grid drawings of graphs. Order 23(1): 1-20, 2006.
  50. V. Dujmović, P. Morin, and D. R. Wood. Layout of graphs with bounded tree-width. SIAM Journal on Computing 34.3: 553-579, 2005.
  51. V. Dujmović and D. R. Wood. Stacks, queues and tracks: Layouts of graph subdivisions. Discrete Mathematics and Theoretical Computer Science 7: 155-202, 2005.
  52. M. Alhashem. The book embeddings of ordered sets. MSc thesis, University of Ottawa, 2005.
  53. V. Dujmović, A. Pór, and D. R. Wood. Track layouts of graphs. Discrete Mathematics & Theoretical Computer Science, 6(2):497-522, 2004.
  54. V. Dujmović and D. R. Wood. On linear layouts of graphs. Discrete Mathematics & Theoretical Computer Science, 6(2):339-358, 2004.
  55. R. Blankenship. Book embeddings of graphs. PhD thesis, Louisiana State University, 2003.
  56. 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.
  57. 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.
  58. 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.
  59. M. Togasaki and K. Yamazaki. Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs. Discrete Mathematics, 259(1-3):361-368, Elsevier, 2002.
  60. J. L. Ganley and L. S. Heath. The pagenumber of k-trees is O(k). Discrete Applied Mathematics, 109(3):215-221, 2001.
  61. 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.
  62. 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.
  63. S. B. Overbay. Generalized book embeddings. PhD thesis, Colorado State University, 1998.
  64. T. Endo. The pagenumber of toroidal graphs is at most seven. Discrete Mathematics, pages 175(1-3):87-96, 1997.
  65. 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.
  66. L. S. Heath, S. V. Pemmaraju. Stack and queue layouts of posets. SIAM Journal on Discrete Mathematics, 10(4):599-625, 1997.
  67. J. L. Ganley. Stack and queue layouts of Halin graphs. manuscript, 1995.
  68. 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.
  69. S. Rengarajan and C. V. Madhavan. Stack and queue number of 2-trees. In International Computing and Combinatorics Conference, pages 203-212. Springer, 1995.
  70. S. M. Malitz. Genus g graphs have pagenumber O(√g). Journal of Algorithms, 17(1):85-109, 1994.
  71. L. S. Heath and S. Istrail. The pagenumber of genus g graphs is O(g). Journal of the ACM , 39(3):479-501, 1992.
  72. 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.
  73. L. S. Heath and A. L. Rosenberg. Laying out graphs using queues. SIAM Journal on Computing, 21(5):927-958, 1992.
  74. M. Yannakakis. Embedding planar graphs in four pages. Journal of Computer and System Sciences, 38(1):36-67, 1989.
  75. L. Heath. Embedding planar graphs in seven pages. In 25th Annual Symposium on Foundations of Computer Science, pages 74-83. IEEE, 1984.
  76. F. Bernhart and P. C. Kainen. The book thickness of a graph. Journal of Combinatorial Theory, Series B, 27(3):320-331, 1979.
  77. G. Ewald. Hamiltonian circuits in simplicial complexes. Geometriae Dedicata 2.1: 115-125, 1973.
  78. 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.