Algorithms for Optimally Shifting Intervals under Intersection Graph Models
This work addresses graph modification problems in computational geometry, offering a novel approach for geometric intersection graphs, though it appears incremental in extending existing graph editing concepts to moving operations.
The paper tackles the problem of modifying geometric intersection graphs by moving objects as an edit operation, introducing the Geometric Graph Edit Distance model, and presents a linear-time algorithm to find the minimum total moving distance to make an interval graph complete, with applications to unit square and unit interval graphs.
In well-studied graph modification problems, adding and deleting vertices and edges are used as graph editing operations. We propose a model for graph modification on geometric intersection graphs called Geometric Graph Edit Distance that moves objects as an edit operation. Our results are mainly focused on interval graphs. In particular, we give a linear-time algorithm to find the minimum total moving distance to render an interval graph complete. The approach of this algorithm can be applied for: (i) rendering a unit square graph complete over the $L_1$ distance and (ii) attaining the existence of a $k$-clique on unit interval graphs. In addition, we provide LP-formulations to achieve several properties in the associated graph of unit intervals.