Overview

Last updated: 2023-04-05
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
genus g 4 [img] gen-ref-BKKPRU20 O(√g) gen-ref-M94
proper minor-closed 4 [img] gen-ref-BKKPRU20 O(1) gen-ref-B03
1-planar 4 gen-ref-ABK15 gen-ref-BKZ15 11 gen-ref-F20
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 4 gen-ref-ABGKP18 49 gen-ref-DJMMUW19
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 495 gen-ref-DMW20
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).


References

  1. An online solver for stack and queue numbers of graphs.
  2. H. Förster, M. Kaufmann, L. Merker, S. Pupyrev, C. Raftopoulou. Linear Layouts of Bipartite Planar Graphs. Algorithms and Data Structures Symposium (WADS), 2023.
  3. P. Jungeblut, L. Merker, and T. Ueckerdt. Directed acyclic outerplanar graphs have constant stack number. Symposium on Foundations of Computer Science, 2023.
  4. 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.
  5. 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.
  6. M Nöllenburg and S Pupyrev. On families of planar DAGs with constant stack number. International Symposium on Graph Drawing, 2023.
  7. L. Merker. Ordered covering numbers. Diss. Karlsruhe Institute of Technology, 2020.
  8. F. Brandenburg. Book embeddings of k-map graphs. arXiv preprint arXiv:2012.06874, 2020.
  9. 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.
  10. 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.
  11. S. Pupyrev. Improved bounds for track numbers of planar graphs. Journal of Graph Algorithms and Applications, pp 323-341, 2020.
  12. V. Dujmović, P. Morin, and D. Wood. Graph product structure for non-minor-closed classes. arXiv preprint arXiv:1907.05168, 2020.
  13. M. Hoffmann and B. Klemz. Triconnected planar graphs of maximum degree five are subhamiltonian. European Symposium on Algorithms (ESA), pp 58, 2019.
  14. X. Guan and W. Yang. Embedding planar 5-graphs in three pages. Discrete Applied Mathematics, 2019.
  15. 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
  16. V. Dujmović and F. Frati. Stack and queue layouts via layered separators. Journal of Graph Algorithms and Applications, pp 89-99, 2018.
  17. J. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, and S. Pupyrev. Queue layouts of planar 3-trees. Algorithmica, pp 1-22, 2020.
  18. 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.
  19. V. Wiechert. On the queue-number of graphs with bounded tree-width. Electr. J. Comb. 24(1), P1.65, 2017.
  20. M. A. Bekos, M. Gronemann, and C. N. Raftopoulou. Two-page book embeddings of 4-planar graphs. Algorithmica, 75(1):158-185, 2016.
  21. M. Alam, F. J. Brandenburg, and S. G. Kobourov. On the book thickness of 1-planar graphs. arXiv preprint arXiv:1510.05891, 2015.
  22. V. Dujmović. Graph layouts via layered separators. Journal of Combinatorial Theory, Series B, 110:79-89, 2015.
  23. 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.
  24. 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.
  25. K. Sperfeld. On the page number of complete odd-partite graphs. Discrete Mathematics, 313(17):1689–1996, 2013.
  26. J. Vandenbussche, W. B. Douglas and Y. Gexin. On the pagenumber of k-trees. SIAM Journal on Discrete Mathematics 23.3: 1455-1464, 2009.
  27. T. Mchedlidze and A. Symvonis. Crossing-free acyclic Hamiltonian path completion for planar st-digraphs. Algorithms and Computation, pp 882-891, 2009.
  28. 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.
  29. V. Dujmović, P. Morin, and D. R. Wood. Layout of graphs with bounded tree-width. SIAM Journal on Computing 34.3: 553-579, 2005.
  30. M. Alhashem. The book embeddings of ordered sets. Master thesis, University of Ottawa, 2005.
  31. V. Dujmović, A. Pór, and D. R. Wood. Track layouts of graphs. Discrete Mathematics & Theoretical Computer Science, 6(2):497-522, 2004.
  32. V. Dujmović and D. R. Wood. On linear layouts of graphs. Discrete Mathematics & Theoretical Computer Science, 6(2):339-358, 2004.
  33. R. Blankenship. Book embeddings of graphs. Ph.D. thesis, Louisiana State University, 2003.
  34. 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.
  35. 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.
  36. 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.
  37. M. Togasaki and K. Yamazaki. Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs. Discrete Mathematics, 259(1-3):361-368, Elsevier, 2002.
  38. J. L. Ganley and L. S. Heath. The pagenumber of k-trees is O(k). Discrete Applied Mathematics, 109(3):215-221, 2001.
  39. 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.
  40. 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.
  41. S. B. Overbay. Generalized book embeddings. PhD thesis, Colorado State University, 1998.
  42. 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.
  43. J. L. Ganley. Stack and queue layouts of Halin graphs. manuscript, 1995.
  44. 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.
  45. S. Rengarajan and C. V. Madhavan. Stack and queue number of 2-trees. In International Computing and Combinatorics Conference, pages 203-212. Springer, 1995.
  46. S. M. Malitz. Genus g graphs have pagenumber O(√g). Journal of Algorithms, 17(1):85-109, 1994.
  47. 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.
  48. L. S. Heath and A. L. Rosenberg. Laying out graphs using queues. SIAM Journal on Computing, 21(5):927-958, 1992.
  49. M. Yannakakis. Embedding planar graphs in four pages. Journal of Computer and System Sciences, 38(1):36-67, 1989.
  50. L. Heath. Embedding planar graphs in seven pages. In 25th Annual Symposium on Foundations of Computer Science, pages 74-83. IEEE, 1984.
  51. F. Bernhart and P. C. Kainen. The book thickness of a graph. Journal of Combinatorial Theory, Series B, 27(3):320-331, 1979.
  52. G. Ewald. Hamiltonian circuits in simplicial complexes. Geometriae Dedicata 2.1: 115-125, 1973.
  53. 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.