Constrained and Ordered Level Planarity Parameterized by the Number of Levels

• Main Authors: Blažej, Václav, Klemz, Boris, Klesen, Felix, Sieper, Marie Diana, Wolff, Alexander, Zink, Johannes
• Other Authors: Václav Blažej and Boris Klemz and Felix Klesen and Marie Diana Sieper and Alexander Wolff and Johannes Zink
• Format: Article in Journal/Newspaper
• Language: English
• Published: Schloss Dagstuhl – Leibniz-Zentrum für Informatik 2024
• Subjects: Parameterized Complexity; Graph Drawing; XNLP; XP; W[t]-hard; Level Planarity; Planar Poset Diagram; Computational Geometry; Groenland
• Online Access: https://doi.org/10.4230/LIPIcs.SoCG.2024.20; https://nbn-resolving.org/urn:nbn:de:0030-drops-199652; https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.20

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.