Upper and Lower Bounds on the Complexity of Unit-Distance Graph Realization in Z d
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
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?