<div class="csl-bib-body">
<div class="csl-entry">Nöllenburg, M., & Pupyrev, S. (2023). On Families of Planar DAGs with Constant Stack Number. In M. A. Bekos & M. Chimani (Eds.), <i>Graph Drawing and Network Visualization : 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II</i> (pp. 135–151). Springer. https://doi.org/10.1007/978-3-031-49272-3_10</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/192836
-
dc.description.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
dc.language.iso
en
-
dc.subject
stack number
en
dc.subject
twist number
en
dc.subject
planar directed acyclic graphs
en
dc.title
On Families of Planar DAGs with Constant Stack Number
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.relation.publication
Graph Drawing and Network Visualization : 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II
-
dc.contributor.affiliation
Meta (United States), United States of America (the)
-
dc.contributor.editoraffiliation
University of Ioannina, Greece
-
dc.relation.isbn
978-3-031-49274-7
-
dc.relation.doi
10.1007/978-3-031-49272-3
-
dc.relation.issn
0302-9743
-
dc.description.startpage
135
-
dc.description.endpage
151
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
tuw.booktitle
Graph Drawing and Network Visualization : 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II
-
tuw.container.volume
14466
-
tuw.relation.publisher
Springer
-
tuw.relation.publisherplace
Cham
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.1007/978-3-031-49272-3_10
-
dc.description.numberOfPages
17
-
tuw.author.orcid
0000-0003-0454-3937
-
tuw.author.orcid
0000-0003-4089-673X
-
tuw.event.name
2023 Graph Drawing and Network Visualization
en
tuw.event.startdate
20-09-2023
-
tuw.event.enddate
22-09-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Palermo
-
tuw.event.country
IT
-
tuw.event.presenter
Nöllenburg, Martin
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openairetype
conference paper
-
item.cerifentitytype
Publications
-
item.grantfulltext
restricted
-
item.languageiso639-1
en
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.fulltext
no Fulltext
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
