Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion
摘要
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 (i) edgeless, (ii) acyclic, and (iii) k-clique-free in \(O(n\log n)\) time, where n is the number of arcs. 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.