Partial Level Planarity Parameterized by the Size of the Missing Graph

Abstract

A level planar drawing of a graph G is crossing-free, has y-monotone edges, and uses levels specified in the input as y-coordinates of vertices. In Partial Level Planarity (PLP), we are given a level planar drawing of a subgraph H of G and are asked to extend it to a drawing of G. Results by Brückner and Rutter [SODA 2017] and Klemz and Rote [ACM Trans. Alg. 2019] show that PLP remains NP-complete even for severely restricted instances, which makes it resistant against parameterized tractability for most well-known parameters. In this paper, we use the size of the missing graph, i.e., of G \ H, as a parameter to identify fixed-parameter tractable fragments of PLP.