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, New York, NY, USA , pp. 329-339 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_33).

Full text not available from this repository.

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.

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

Repository Staff Only: item control page

References

A. G. Bell, "Tetrahedral principle in kite structure", National Geographic Magazine, 14(6), June 1903, pp. 219-251.

R. Buckminster Fuller. Inventions, the Patented Works of R. Buckminster Fuller. St. Martin's Press, 1983.

P. Bose, W. Lenhart, and G. Liotta, "Characterizing proximity trees", Algorithmica, 16, 1996, pp. 83-110, 1996.

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.

G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis. Graph Drawing. Prentice Hall, 1999, Chapter 11.2.

M. B. Dillencourt, "Realizability of Delaunay triangulations", Informa. Process. Lett., 33(6), Feb. 1990, pp.283-287.

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.

P. Eades and S. Whitesides, "The logic engine and the realization problem for nearest neighbour graphs", Theoretical Computer Science, 169, 1996, pp. 23-37.

P. Eades and S. Whitesides, "The realization problem for Euclidean minimum spanning trees is NP-hard", Algorithmica, 16, 1996, pp. 60-82.

M. Garey and D. Johnson. Computers and Intractability:a Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.

J. W. Jaromczyk and G. T. Toussaint, "Relative neighborhood graphs and their relatives", Proc. IEEE, 80(9), 1992, pp. 1502-1517.

W. Lenhart and G. Liotta, "The drawability problem for minimum weight triangulations", Theoret. Comp. Sci. vol. 27, 2002, pp. 261-286.

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.

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.

G. Liotta and H. Meijer, "Drawing of trees", Computational Geometry: Theory and Applications, 24(3), 2003, pp. 147-178.

G. Toussaint, "A graph-theoretical primal sketch", in Computational Morphology. North-Holland, 1988, pp. 229-260.