Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.20903 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910106295205888 |
|---|---|
| author | Honorato-Droguett, Nicolás Kurita, Kazuhiro Hanaka, Tesshu Ono, Hirotaka Wolff, Alexander |
| author_facet | Honorato-Droguett, Nicolás Kurita, Kazuhiro Hanaka, Tesshu Ono, Hirotaka Wolff, Alexander |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_20903 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion Honorato-Droguett, Nicolás Kurita, Kazuhiro Hanaka, Tesshu Ono, Hirotaka Wolff, Alexander Computational Geometry 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. |
| title | Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2509.20903 |