Constrained and Ordered Level Planarity Parameterized by the Number of Levelswith Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink
We are given a graph where each vertex is assigned a position with an arbitrary x-coordinate, but y-coordinate being 1 to $k$. The question is whether it is possible to embed the edges in a planar way so that each edge is y-monotone – meaning from the lower vertex the edge always increases in y-coordinate until it reaches the other vertex.
Note the problem can also be posed as having the vertices assigned to horizontal lines and given their left-to-right order. Our original investigation concerned the case where the order is not total (called constrained level planarity). For that variant it was known that 2 levels are easy and 5 levels are NP-hard (by a reduction from 3-partition). We improved the hardness to 4 levels and 3 levels were investigated deeper. It turns out that 3 levels can be solved, but the algorithm is quite complex.
The main part of the paper looks at the total-order variant and asks what is its parameterized complexity with respect to the number of levels. We noticed that a sweep line DP reaches XP quite easily. Then we built W-hardness reduction from multicolored independent set. And last we noticed that the linear structure of the problem allows us to chain the reduced instances – leading to XNLP-hardness (which notably implies that the problem is W[t]-hard for every t). The construction heavily depended on a sequence of disconnected components that “shift” around to model vertex selection. So as the last step, we showed one can increase the number of levels to $O(k^2)$ and alter the construction to also have a path from each component to a single topmost vertex, making the construction connected.