For a fixed graph class Π, the goal of Π-Modification is to transform an input graph G into a graph H ∈ Π using at most k modifications. Vertex and edge deletions are common operations, and their (parameterized) complexity for various Π is well-studied. Classic graph modification operations such as edge deletion do not consider the geometric nature of intersection graphs such as (unit) disk graphs. This led Fomin et al. [ITCS' 25] to introduce scaling as a geometric graph modification operation for unit disk graphs: For a given radius r, each modified disk will be rescaled to radius r. In this paper, we generalize their model by allowing rescaled disks to choose a radius within a given interval [r_min, r_max] and study the (parameterized) complexity (with respect to k) of the corresponding problem Π-Scaling. We show that Π-Scaling is in XP for every graph class Π that can be recognized in polynomial time. Furthermore, we show that Π-Scaling: (1) is NP-hard and FPT for cluster graphs, (2) can be solved in polynomial time for complete graphs, and (3) is W[1]-hard for connected graphs. In particular, (1) and (2) answer open questions of Fomin et al. and (3) generalizes the hardness result for their variant where the set of scalable disks is restricted.

A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with "tracks" for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.

Boundary labeling is a technique in computational geometry used to label sets of features in an illustration. It involves placing labels along an axis-parallel bounding box and connecting each label with its corresponding feature using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: Grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP -hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Furthermore, we show that finding a labeling on two opposite sides of the boundary is NP -complete, even for uniform-height labels and finite label positions. Finally, we experimentally confirm that our approach has also practical relevance.

Boundary labeling is a technique in computational geometry used to label sets of features in an illustration. It involves placing labels along an axis-parallel bounding box and connecting each label with its corresponding feature using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: Grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Furthermore, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions. Finally, we experimentally confirm that our approach has also practical relevance.