Depian, T., Fink, S. D., Klemz, B., Ganian, R., Nöllenburg, M., & Sieper, M. D. (2025). Partial Level Planarity Parameterized by the Size of the Missing Graph. In EUROCG’25 Booklet of Abstracts. EuroCG 2025, Liblice, Czechia.
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.
