Report
Parameterized Algorithms for Upward Planarity
| العنوان: | Parameterized Algorithms for Upward Planarity |
|---|---|
| المؤلفون: | Chaplick, Steven, Di Giacomo, Emilio, Frati, Fabrizio, Ganian, Robert, Raftopoulou, Chrysanthi N., Simonov, Kirill |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computational Geometry, Computer Science - Data Structures and Algorithms |
| الوصف: | 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. Comment: To appear at the 38th International Symposium on Computational Geometry (SoCG 2022) |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2203.05364 |
| رقم الانضمام: | edsarx.2203.05364 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |