On the recognition of unit disk graphs and the Distance Geometry Problem with Ranges

We introduce a method to decide whether a graph GG admits a realization on the plane in which two vertices lie within unitary distance from one another exactly if they are neighbors in GG. Such graphs are called unit disk graphs, and their recognition is a known NP-hard problem. By iteratively discretizing the plane, we build a sequence of geometrically defined trigraphs–graphs with mandatory, forbidden and optional adjacencies–until either we find a realization of GG or the interruption of such a sequence certifies that no realization exists. Additionally, we consider the proposed method in the scope of the more general Distance Geometry Problem with Ranges, where arbitrary intervals of pairwise distances are allowed.