Determining unit distance graphs with coordinates in ${\mathbb{Z}}^2$ is NP-complete

Abstract

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.

arXiv commentIt turns out that this result is already known. A stronger result (about unit-distance trees instead of arbitrary graphs) is: Sandeep N. Bhatt, Stavros S. Cosmadakis, The complexity of minimizing wire lengths in VLSI layouts, 1987