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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion

  • Nicolás Honorato-Droguett,
  • Kazuhiro Kurita,
  • Tesshu Hanaka,
  • Hirotaka Ono,
  • Alexander Wolff

摘要

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.