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 , pp. 47-51(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item