A Characterization in Zn of Finite Unit-Distance Graphs in Rn

AbstractA unit-distance graph in Rn is a graph with a subset of Rn as the vertex set and two vertices adjacent only if their Euclidean distance is one. It is shown that a finite graph G on m vertices is isomorphic to a unit-distance graph in Rn if and only if there exists a real number λ and for arbitrarily large integer r the graph G can be drawn in the n-dimensional integer lattice Zn such that (i) the distance between every pair of vertices is at least λr and (ii) adjacent vertices have their distance in the closed interval [r − g(r), r + g(r)] with g(r) = 2 √n/r1/nm. In the case of the Euclidean plane two variations of this result are proved