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