Is realization of unit disk graphs hard?
One of the complications here is that there is no natural &quot;decision variant&quot; of this problem, since this isn't an optimization problem. (and the problem &quot;given an UDG, is there a realization?&quot; is trivial)
Since reductions between decision problems tend to be better studied, one option is to make it an optimisation problem in a chosen parameter. Even though you don't care about that value, you can use binary search on the optimisation problem to solve the realisation problem. Hence, the realisation problem is not much easier than the opt. problem, so showing the opt. problem is hard suffices.
The question then of course is what parameter to choose. Perhaps the problem &quot;Given an UDG, find a realisation with minimum/maximum sum of edge lengths&quot; would be suitable. It seems related to the problem that Aspnes et al. [1] show to be NP-hard.

[1]: ASPNES, James, et al. A theory of network localization. IEEE Transactions on Mobile Computing, 2006, 5.12: 1663-1678.