Three-Dimensional Grid Drawings with Sub-quadratic Volume

Dujmović, Vida and Wood, David R. (2004) Three-Dimensional Grid Drawings with Sub-quadratic Volume. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 190-201(Official URL:

Full text not available from this repository.


A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise non-crossing. A O(n^3/2) volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was O(m^2). These results (partially) solve open problems due to Pach, Thiele, and Tóth [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001].

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_18
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.720 Straight-line
P Styles > P.060 3D

Actions (login required)

View Item View Item