Upward and Rectilinear Planarity are W[1]-Hard Parameterized by Treewidth
SIAM Journal on Discrete Mathematics · 30.06.2026 · 40 (2) · 706-742
DOI: 10.1137/24m1679240 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 13.05.2026. Verfasst von Bart M. P. Jansen und 5 weiteren Autor:innen. Die Arbeit nennt 43 Literaturangaben. Gefördert von: Horizon 2020 Framework Programme, Vienna Science and Technology Fund, Austrian Science Fund.
Abstract (Originalsprache)
Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both [Formula: see text]-complete but [Formula: see text] when parameterized by treewidth. In this paper we show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known [Formula: see text]-time algorithms cannot be improved to run in time [Formula: see text] unless the exponential time hypothesis fails.
Förderung
- Horizon 2020 Framework Programme
- Vienna Science and Technology Fund
- Austrian Science Fund
- MUR of Italy
- Deutsche Forschungsgemeinschaft
Zitieren
APA
Jansen, B. M. P., Khazaliya, L., Kindermann, P., Liotta, G., Montecchiani, F., & Simonov, K. (2026). Upward and Rectilinear Planarity are W[1]-Hard Parameterized by Treewidth. SIAM Journal on Discrete Mathematics, 40(2), 706-742. https://doi.org/10.1137/24m1679240
Vancouver
Jansen BMP, Khazaliya L, Kindermann P, Liotta G, Montecchiani F, Simonov K. Upward and Rectilinear Planarity are W[1]-Hard Parameterized by Treewidth. SIAM Journal on Discrete Mathematics. 2026;40(2):706-742. doi:10.1137/24m1679240
BibTeX
@article{Jansen2026,
author = {Jansen, Bart M. P. and Khazaliya, Liana and Kindermann, Philipp and Liotta, Giuseppe and Montecchiani, Fabrizio and Simonov, Kirill},
title = {Upward and Rectilinear Planarity are W[1]-Hard Parameterized by Treewidth},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {2},
pages = {706--742},
doi = {10.1137/24m1679240}
}
EUVIMED