%0 Generic
%A Kitching, Matthew
%A Whitesides, Sue
%D 2004
%E Pach, János
%F gdea_3:599
%I Springer
%P 329-339
%T The Three Dimensional Logic Engine
%U http://gdea.informatik.uni-koeln.de/599/
%X We consider the following graph embedding question: given a graph G, is it possible to map its vertices to points in 3D such that G is isomorphic to the mutual nearest neighbor graph of the set P of points to which the vertices are mapped? We show that this problem is NP-hard. We do this by extending the "logic engine" method to three dimensions by using building blocks inpired by the structure of diamond and by constructions of A.G. Bell and B. Fuller.