CCMay 21
Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
arXiv:2510.1500211.0
Predicted impact top 28% in CC · last 90 daysOriginality Highly original
AI Analysis
This resolves a long-standing open problem in computational geometry by establishing the NP-completeness of unit-distance graph realizability in Z^2.
The paper proves that deciding whether a graph can be realized as a unit-distance graph with integer coordinates in the plane is NP-complete, by reducing from NA3SAT.
The problem of determining whether a graph $G$ can be realized as a unit-distance graph in $\mathbb{Z}^2$ is NP-complete. As far as we can tell, a proof of this result has never been written up. We prove NP-completeness of this problem by implementing Eades and Whitesides' logic engine in this setting, and construct a graph that is realizable if and only if an arbitrary NA3SAT formula is satisfiable.