Moving Geometric Objects to Render Their Intersection Graph Connected or Locally Dense

In this paper, we study graph editing problems on geometric intersection graphs. For a tuple $\mathcal{S}=(S_1,\dots ,S_n)$ of geometric objects in some Euclidean space, let $G_{\mathcal{S}}$ be their intersection graph. We study the problem of finding a tuple $D=(d_1,\dots ,d_n)$ of movement vectors such that the resulting intersection graph $G_{\mathcal{S}+D}$ (after moving, for every $i\in \{1,\dots ,n\}$, object $S_i$ by $d_i$) has a predefined property and the total movement distance $|D|$ is minimum. In the weighted version, we are also given a weight vector $w=(w_1,\dots ,w_n)$ with positive entries, and the objective is to minimise the total weighted movement distance $|w\cdot D|$. We first consider the property locally dense, which we define as containment of a $k$-clique. Given $n$ weighted intervals, we solve the problem with respect to this property in $O(k^{1/3}n{\log }^{1+\epsilon }n)$ time for any $\epsilon >0$. We then consider $k$-connectivity for $1\le k\le n-1$. Given $n$ unweighted unit intervals, we solve the problem in $O(n^2\log n)$ time and, for $k=1$, in $O(n\log n)$ time. For $k=1$, we prove strong NP-hardness on intervals of arbitrary length and on weighted unit disks (with only two distinct weights), and weak NP-hardness on weighted intervals (even when lengths equal weights).