Three-Dimensional Grid Drawings of Graphs

Pach, János and Thiele, Torsten and Tóth, Géza (1998) Three-Dimensional Grid Drawings of Graphs. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 47-51 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_49).

Full text not available from this repository.

Abstract

A three-dimensional grid drawing of a graph G is a placement of the vertices at distinct integer points so that the straight-line segments representing the edges of G are pairwise non-crossing. It is shown that for any fixed r \geq 2, every r-colorable graph of n vertices has a three-dimensional grid drawing that fits into a box of volume O(n^{2}). The order of magnitude of this bound cannot be improved.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_49
Classifications:P Styles > P.060 3D
ID Code:171

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis, Algorithms for drawing graphs: an annotated bibliography, Computational Geometry: Theory and Applications 4 (1994), 235-282.

R.F. Cohen, P. Eades, T. Lin, and F. Ruskey, Three-dimensional graph drawing, in: Graph Drawing (GD '94, R. Tamassia and I.G. Tollis, eds.), Lecture Notes in Computer Science 1027, Springer-Verlag, Berlin, 1995, 1-11.

T. Calamoneri and A. Sterbini, Drawing 2-, 3-, 4-colorable graphs in O(n^{2}) volume, in: Graph Drawing (GD '96, S. North, ed.), Lecture Notes in Computer Science 1190, Springer-Verlag, Berlin, 1997, 53-62.

H. de Fraysseix, J. Pach, and R. Pollack, How to draw a planar graph on a grid, Combinatorica 10 (1990), 41-51.

G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, University Press, Oxford, 1954.

J. Mackinley, G. Robertson, and S. Card, Cone Trees: Animated 3d visualizations of hierarchical information, in Proceedings of SIGCHI Conference on Human Factors in Computing, 1991, 189-194.

W. Schnyder, Embedding planar graphs on the grid, in Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, 1990, 138-148.