Overview

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 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 2 [img] 31 gen-ref-DJMMUW19
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

References

  1. An online solver for stack and queue numbers of graphs.
  2. L. Merker. Ordered Covering Numbers. Diss. Karlsruhe Institute of Technology, 2020.
  3. F. Brandenburg. Book Embeddings of k-Map Graphs. arXiv preprint arXiv:2012.06874, 2020.
  4. 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.
  5. 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.
  6. S. Pupyrev. Improved Bounds for Track Numbers of Planar Graphs. Journal of Graph Algorithms and Applications, pp 323-341, 2020.
  7. V. Dujmović, P. Morin, and D. Wood. Graph product structure for non-minor-closed classes. arXiv preprint arXiv:1907.05168, 2020.
  8. M. Hoffmann and B. Klemz. Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian. European Symposium on Algorithms (ESA), pp 58, 2019.
  9. X. Guan and W. Yang. Embedding planar 5-graphs in three pages. Discrete Applied Mathematics, 2019.
  10. 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
  11. V. Dujmović and F. Frati. Stack and queue layouts via Layered Separators. Journal of Graph Algorithms and Applications, pp 89-99, 2018.
  12. J. Alam, M. A. Bekos, M. Gronemann, M. Kaufmann, and S. Pupyrev. Queue Layouts of Planar 3-Trees. Algorithmica, pp 1-22, 2020.
  13. 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.
  14. V. Wiechert. On the queue-number of graphs with bounded tree-width. Electr. J. Comb. 24(1), P1.65, 2017.
  15. M. A. Bekos, M. Gronemann, and C. N. Raftopoulou. Two-page book embeddings of 4-planar graphs. Algorithmica, 75(1):158-185, 2016.
  16. M. Alam, F. J. Brandenburg, and S. G. Kobourov. On the book thickness of 1-planar graphs. arXiv preprint arXiv:1510.05891, 2015.
  17. V. Dujmović. Graph layouts via layered separators. Journal of Combinatorial Theory, Series B, 110:79-89, 2015.
  18. M. A. Bekos, M. Kaufmann, and C. Zielke. The book embedding problem from a SAT-solving perspective. International Symposium on Graph Drawing, pages 125-138, 2015.
  19. J. Vandenbussche, W. B. Douglas and Y. Gexin. On the pagenumber of k-trees. SIAM Journal on Discrete Mathematics 23.3: 1455-1464, 2009.
  20. 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.
  21. V. Dujmović, P. Morin, and D. R. Wood. Layout of graphs with bounded tree-width. SIAM Journal on Computing 34.3: 553-579, 2005.
  22. V. Dujmović, A. Pór, and D. R. Wood. Track layouts of graphs. Discrete Mathematics & Theoretical Computer Science, 6(2):497-522, 2004.
  23. V. Dujmović and D. R. Wood. On linear layouts of graphs. Discrete Mathematics & Theoretical Computer Science, 6(2):339-358, 2004.
  24. R. Blankenship. Book Embeddings of Graphs. Ph.D. thesis, Louisiana State University, 2003.
  25. 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.
  26. 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.
  27. 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.
  28. M. Togasaki and K. Yamazaki. Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs. Discrete Mathematics, 259(1-3):361-368, Elsevier, 2002.
  29. J. L. Ganley and L. S. Heath. The pagenumber of k-trees is O(k). Discrete Applied Mathematics, 109(3):215-221, 2001.
  30. S. B. Overbay. Generalized book embeddings. PhD thesis, Colorado State University, 1998.
  31. 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.
  32. J. L. Ganley. Stack and queue layouts of Halin graphs. manuscript, 1995.
  33. 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.
  34. S. Rengarajan and C. V. Madhavan. Stack and queue number of 2-trees. In International Computing and Combinatorics Conference, pages 203-212. Springer, 1995.
  35. S. M. Malitz. Genus g graphs have pagenumber O(√g). Journal of Algorithms, 17(1):85-109, 1994.
  36. 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.
  37. L. S. Heath and A. L. Rosenberg. Laying out graphs using queues. SIAM Journal on Computing, 21(5):927-958, 1992.
  38. M. Yannakakis. Embedding planar graphs in four pages. Journal of Computer and System Sciences, 38(1):36-67, 1989.
  39. L. Heath. Embedding planar graphs in seven pages. In 25th Annual Symposium on Foundations of Computer Science, pages 74-83. IEEE, 1984.
  40. F. Bernhart and P. C. Kainen. The book thickness of a graph. Journal of Combinatorial Theory, Series B, 27(3):320-331, 1979.
  41. G. Ewald. Hamiltonian circuits in simplicial complexes. Geometriae Dedicata 2.1: 115-125, 1973.
  42. 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.