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

Eric Binnendyk

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 be…