2018/11/30 by Édouard Bonnet, Sergio Cabello, Bonnet, Édouard +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1811.12547
openalex publication_date 2018/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the inverse Voronoi diagram problem in graphs: given a graph G with positive edge-lengths and a collection \mathbbU of subsets of vertices of V(G), decide whether \mathbbU is a Voronoi diagram in G with respect to the shortest-path metric. We show that the problem is NP-hard, even for planar graphs where all the edges have unit length. We also study the parameterized complexity of the problem and show that the problem is W[1]-hard when parameterized by the number of Voronoi cells or by the pathwidth of the graph. For trees we show that the problem can be solved in O(N+n log2 n) time, where n is the number of vertices in the tree and N=n+∑_U∈ \mathbbU|U| is the size of the description of the input. We also provide a lower bound of Ω(n log n) time for trees with n vertices.