THE LOGIC ENGINE AND THE REALIZATION PROBLEM FOR NEAREST-NEIGHBOR GRAPHS

Roughly speaking, a ''nearest neighbor graph'' is formed from a set of points in the plane by joining two points if one is the nearest neigh bor of the other. There are several ways in which this intuitive conce pt can be made precise. This paper investigates the complexity of dete rmining whether, for a given graph G, there is a set of points P in th e plane such that G is isomorphic to a nearest neighbor graph on P. We show that this problem is NP-hard for several definitions of nearest neighbor graph. Our proof technique uses an interesting simulation of a mechanical device called a ''logic engine''.