Upper and Lower Bounds on the Complexity of Unit-Distance Graph Realization in Zᵈ

It is known that the problem of recognizing the existence of a unit-distance realization in Zᵈ for a graph G is NP-complete. Here, assuming ETH, we give a sub-exponential lower bound of 2Ω(√n) for this problem in Z² and 2^Ω(n2/3) in Z³, and give an upper bound of 2^O(n(d-1)/d (log n)²) for the time complexity with an explicit divide-and-conquer algorithm. This approach beats naive exhaustive search by a factor of Ω(n1/d) in the exponent. For 2 and 3 dimensions, our upper and lower bounds match to within a logarithmic factor.