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.), 38th International Symposium on Computational Geometry (SoCG 2022) (pp. 1–16). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2022.26
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
Project title:
Parameterisierte Analyse in der Künstlichen Intelligenz: Y1329-N (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) New Frontiers for Parameterized Complexity: P31336-N35 (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
CC BY 4.0
