Monotone Clustered Level Planarity
2026-07-20 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational Geometry
AI summaryⓘ
The authors study a problem called monotone Clustered Level Planarity (mCLP), which combines two graph drawing rules: organizing nodes by levels and grouping them into clusters that stay connected. They build on previous work by Fink et al., who showed mCLP is hard to solve even for simple cases. The authors further prove that this difficulty remains for many graph types and parameters, except when considering vertex cover and cluster count together. They also explain that usual simplification methods don't work well here because mCLP behaves unpredictably on smaller parts of the graph.
level planarityclustered planaritymonotone Clustered Level Planarity (mCLP)NP-completenessparameterized complexityfixed-parameter tractabilityvertex covergraph augmentationgraph drawingnon-hereditary problem
Authors
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter, Marie Diana Sieper
Abstract
We consider the combination of the two constrained planarity problems Level- and Clustered Planarity. Traditionally, level-planar drawings with convex clusters have been studied in this setting. Fink et al. (EuroCG 2024) recently introduced a different way of combining level- and clustered planarity by mimicking a classic characterization of clustered planarity in the level-planar setting: The problem (y-)monotone Clustered Level Planarity (mCLP) seeks a level-planar drawing in which it is possible to augment each cluster with edges that do not cross cluster boundaries so that it becomes connected while maintaining level-planarity. This is in line with previous research on clustered planarity that poses certain requirements on the augmentation edges that make each cluster connected, e.g., that they form a path. Fink et al. (EuroCG 2024) showed that mCLP is NP-complete even for biconnected single-source graphs and instances with a constant number of levels and clusters. We further classify the parameterized complexity of the mCLP problem by, on the one hand, showing hardness even for instances that consist of a forest with trees of bounded size, no isolated vertices, and a small constant number of either clusters or levels. This excludes fixed-parameter tractability for almost all graph-structural parameters, except for vertex cover, even in conjunction with the number of clusters. We complement this by showing fixed-parameter tractability when parameterizing by the vertex cover number and the number of clusters. A major obstacle is the fact that mCLP is non-hereditary, i.e., subinstances of yes-instances may be no-instances and vice versa, which makes it challenging to apply usual reduction techniques.