  We introduce the inverse Voronoi diagram problem in graphs: given a graph $G$
with positive edge-lengths and a collection $\mathbb{U}$ of subsets of vertices
of $V(G)$, decide whether $\mathbb{U}$ 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 \log^2 n)$
time, where $n$ is the number of vertices in the tree and $N=n+\sum_{U\in
\mathbb{U}}|U|$ is the size of the description of the input. We also provide a
lower bound of $\Omega(n \log n)$ time for trees with $n$ vertices.
