Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion
This addresses overlap removal in scheduling and map labelling, but the results are incremental extensions of prior work on geometric graph edit distance.
The paper tackles the problem of removing overlaps in geometric intersection graphs by minimizing movement distances, presenting an O(n log n) algorithm for unit circular arcs to make graphs edgeless and k-clique-free, and proving strong NP-hardness for various graph classes including interval graphs and d-balls/cubes.
Removing overlaps is a central task in domains such as scheduling, visibility, and map labelling. This can be modelled using graphs, where overlap removals correspond to enforcing a certain sparsity constraint on the graph structure. We continue the study of the problem Geometric Graph Edit Distance (GGED), where the aim is to minimise the total cost of editing a geometric intersection graph to obtain a graph contained in a specific graph class. For us, the edit operation is the movement of objects, and the cost is the movement distance. We present an algorithm for rendering the intersection graph of a set of unit circular arcs edgeless and $k$-clique-free in $O(n\log n)$ time, where $n$ is the number of arcs. The algorithm can be also used to solve an open case of the points-spreading problem on cyclic domains [Li \& Wang, CGT 2025]. We also show that GGED remains strongly NP-hard on unweighted interval graphs, solving an open problem of Honorato-Droguett et al. [WADS 2025]. We complement this result by showing that GGED is strongly NP-hard on sets of $d$-balls and $d$-cubes, for any $d\ge 2$. Finally, we present an XP algorithm (parameterised by the number of maximal cliques) that removes all edges from the intersection graph of a set of weighted unit intervals.