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

arXiv:2610.36516 · cs.CC · Submitted 2026-10-27 · Read on arXiv

cs.CC

Submitted: 2026-10-27

Updated: 2026-10-27

License: http://creativecommons.org/licenses/by/4.0/

The gist: It is known that the problem of recognizing the existence of a unit-distance realization in Z d for a graph G is NP-complete.

Abstract

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

Related papers