Constrained Level Planarity

Level Planarity is a graph drawing problem that involves representing a given graph in a plane drawing such that the vertices of the graph are placed on a sequence of horizontal lines, or “levels.” Target level of each vertex is given and the vertices should be placed in such a way that the edges of the graph drawn as line segments are non-crossing. We consider Constrained Level Planarity which is a generalization of the Level Planarity problem where the vertices of the graph are subject to additional constraints on their order within the levels. We show that this problem is polynomial-time solvable for at most \(3\) levels and is \(\mathsf{NP}\)-complete if the number of levels is at least \(4\).