<div class="csl-bib-body">
<div class="csl-entry">Chaplick, S., Di Giacomo, E., Frati, F., Ganian, R., Raftopoulou, C., & Simonov, K. (2022). Parameterized Algorithms for Upward Planarity. In X. Goaoc & M. Kerber (Eds.), <i>38th International Symposium on Computational Geometry (SoCG 2022)</i> (pp. 1–16). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2022.26</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/150298
-
dc.description.abstract
We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-parameter algorithm parameterized by the number of sources, an XP-algorithm parameterized by treewidth, and a fixed-parameter algorithm parameterized by treedepth. All three algorithms are obtained using a novel framework for the problem that combines SPQR tree-decompositions with parameterized techniques. Our approach unifies and pushes beyond previous tractability results for the problem on series-parallel digraphs, single-source digraphs and outerplanar digraphs.
en
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.relation.isversionof
https://doi.org/10.48550/arXiv.2203.05364
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
parameterized algorithms
en
dc.subject
SPQR trees
en
dc.subject
treedepth
en
dc.subject
treewidth
en
dc.subject
Upward planarity
en
dc.title
Parameterized Algorithms for Upward Planarity
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.contributor.affiliation
Maastricht University, The Netherlands
-
dc.contributor.affiliation
Università degli Studi di Perugia, Italy
-
dc.contributor.affiliation
Roma Tre University, Rome, Italy
-
dc.contributor.affiliation
National Technical University of Athens, Greece
-
dc.contributor.editoraffiliation
Université de Lorraine, CNRS, Inria, LORIA, Nancy, France