creators_name: Kitching, Matthew
creators_name: Whitesides, Sue
editors_name: Pach, János
editors_id: Pach, János
type: confpaper
datestamp: 2005-07-21
lastmod: 2008-09-18 11:08:55
metadata_visibility: show
title: The Three Dimensional Logic Engine
ispublished: pub
subjects: Z.250
full_text_status: none
abstract: 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.
date: 2004
date_type: published
publisher: Springer
pagerange: 329-339
refereed: FALSE
referencetext: 1. A. G. Bell, "Tetrahedral principle in kite structure", National Geographic Magazine, 14(6), June 1903, pp. 219-251.
2. R. Buckminster Fuller. Inventions, the Patented Works of R. Buckminster Fuller. St. Martin's Press, 1983.
3. P. Bose, W. Lenhart, and G. Liotta, "Characterizing proximity trees", Algorithmica, 16, 1996, pp. 83-110, 1996.
4. F. J. Brandenburg, D. Eppstein, M. T. Goodrich, S. G. Kobourov, G. Liotta, and P. Mutzel, "Selected open problems in graph drawing", Proc. 11th Int. Symp. Graph Drawing, 2003, Springer-Verlag LNCS vol. 2912, pp. 515-539.
5. G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis. Graph Drawing. Prentice Hall, 1999, Chapter 11.2.
6. M. B. Dillencourt, "Realizability of Delaunay triangulations", Informa. Process. Lett., 33(6), Feb. 1990, pp.283-287.
7. M. B. Dillencourt and W. D. Smith, "Graph-theoretical conditions for inscribability and Delaunay realizability", Proc. 6th Canad. Conf. Comput. Geom., 1994, pp. 287-292.
8. P. Eades and S. Whitesides, "The logic engine and the realization problem for nearest neighbour graphs", Theoretical Computer Science, 169, 1996, pp. 23-37.
9. P. Eades and S. Whitesides, "The realization problem for Euclidean minimum spanning trees is NP-hard", Algorithmica, 16, 1996, pp. 60-82.
10. M. Garey and D. Johnson. Computers and Intractability:a Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
11. J. W. Jaromczyk and G. T. Toussaint, "Relative neighborhood graphs and their relatives", Proc. IEEE, 80(9), 1992, pp. 1502-1517.
12. W. Lenhart and G. Liotta, "The drawability problem for minimum weight triangulations", Theoret. Comp. Sci. vol. 27, 2002, pp. 261-286.
13. G. Liotta and G. Di Battista "Computing proximity drawings of trees in the 3-dimensional space", Proc. 4th Workshop Algorithms and Data Structures WADS 1995, Springer-Verlag LNCS vol. 955, pp. 239-250.
14. G. Liotta, A. Lubiw, H. Meijer, and S. H. Whitesides, "The rectangle of influence drawability problem", Comput. Geom. Theory Appl., 10(1):1-22, 1998.
15. G. Liotta and H. Meijer, "Drawing of trees", Computational Geometry: Theory and Applications, 24(3), 2003, pp. 147-178.
16. G. Toussaint, "A graph-theoretical primal sketch", in Computational Morphology. North-Holland, 1988, pp. 229-260.

citation: Kitching, Matthew and Whitesides, Sue (2004) The Three Dimensional Logic Engine. [Conference Paper]