title: The Three Dimensional Logic Engine
creator: Kitching, Matthew
creator: Whitesides, Sue
subject: Z.250 Geometry
description: 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.
publisher: Springer
contributor: Pach, János
date: 2004
type: Conference Paper
type: NonPeerReviewed
identifier: Kitching, Matthew and Whitesides, Sue (2004) The Three Dimensional Logic Engine. [Conference Paper]
relation: http://gdea.informatik.uni-koeln.de/599/