Record link: 
http://hdl.handle.net/20.500.12708/192836
-
Title: 
On Families of Planar DAGs with Constant Stack Number
en
Citation: 
Nöllenburg, M., & Pupyrev, S. (2023). On Families of Planar DAGs with Constant Stack Number. In M. A. Bekos & M. Chimani (Eds.), Graph Drawing and Network Visualization : 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II (pp. 135–151). Springer. https://doi.org/10.1007/978-3-031-49272-3_10
-
Publisher DOI: 
10.1007/978-3-031-49272-3_10
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Nöllenburg, Martin 
Pupyrev, Sergey 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Graph Drawing and Network Visualization : 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II 
-
ISBN: 
978-3-031-49274-7
-
Volume: 
14466
-
DOI of the book: 
10.1007/978-3-031-49272-3
-
Date (published): 
1-Jan-2023
-
Event name: 
2023 Graph Drawing and Network Visualization 
en
Event date: 
20-Sep-2023 - 22-Sep-2023
-
Event place: 
Palermo, Italy
-
Number of Pages: 
17
-
Publisher: 
Springer, Cham
-
Keywords: 
stack number; twist number; planar directed acyclic graphs
en
Abstract: 
A k-stack layout (or k-page book embedding) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing edges with respect to the vertex order. The stack number of a graph is the minimum k such that it admits a k-stack layout. In this paper we study a long-standing problem regarding the stack number of planar directed acyclic graphs (DAGs), for which the vertex order has to respect the orientation of the edges. We investigate upper and lower bounds on the stack number of several families of planar graphs: We improve the constant upper bounds on the stack number of single-source and monotone outerplanar DAGs and of outerpath DAGs, and improve the constant upper bound for upward planar 3-trees. Further, we provide computer-aided lower bounds for upward (outer-) planar DAGs.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

79
checked on Jan 26, 2024

Download(s)

2
checked on Jan 26, 2024

Google ScholarTM

Check