The Three Dimensional Logic Engine

Kitching, Matthew and Whitesides, Sue (2004) The Three Dimensional Logic Engine. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 329-339(Official URL:

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_33
Classifications: Z Theory > Z.250 Geometry

Actions (login required)

View Item View Item