2026-07-22T01:57:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19965 2024-06-06T06:21:13Z ddc:004 open_access

Constrained and Ordered Level Planarity Parameterized by the Number of Levels Blažej, Václav Klemz, Boris Klesen, Felix Sieper, Marie Diana Wolff, Alexander Zink, Johannes Parameterized Complexity Graph Drawing XNLP XP W[t]-hard Level Planarity Planar Poset Diagram Computational Geometry The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every edge is realized as a y-monotone curve. In the variant Constrained Level Planarity (CLP), each level y is equipped with a partial order ≺_y on its vertices and in the desired drawing the left-to-right order of vertices on level y has to be a linear extension of ≺_y. Ordered Level Planarity (OLP) corresponds to the special case of CLP where the given partial orders ≺_y are total orders. Previous results by Brückner and Rutter [SODA 2017] and Klemz and Rote [ACM Trans. Alg. 2019] state that both CLP and OLP are NP-hard even in severely restricted cases. In particular, they remain NP-hard even when restricted to instances whose width (the maximum number of vertices that may share a common level) is at most two. In this paper, we focus on the other dimension: we study the parameterized complexity of CLP and OLP with respect to the height (the number of levels). We show that OLP parameterized by the height is complete with respect to the complexity class XNLP, which was first studied by Elberfeld, Stockhusen, and Tantau [Algorithmica 2015] (under a different name) and recently made more prominent by Bodlaender, Groenland, Nederlof, and Swennenhuis [FOCS 2021]. It contains all parameterized problems that can be solved nondeterministically in time f(k)⋅ n^O(1) and space f(k)⋅ log n (where f is a computable function, n is the input size, and k is the parameter). If a problem is XNLP-complete, it lies in XP, but is W[t]-hard for every t. In contrast to the fact that OLP parameterized by the height lies in XP, it turns out that CLP is NP-hard even when restricted to instances of height 4. We complement this result by showing that CLP can be solved in polynomial time for instances of height at most 3. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Václav Blažej and Boris Klemz and Felix Klesen and Marie Diana Sieper and Alexander Wolff and Johannes Zink 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.20 urn:nbn:de:0030-drops-199652 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.20 eng https://creativecommons.org/licenses/by/4.0/legalcode