The Maximum Number of Edges in a Three-Dimensional Grid-Drawing
Vol. 8, no. 1, pp. 21-26, 2004. Concise paper.
Abstract An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of three-dimensional grid-drawings is obtained as a corollary. Our results generalise to the setting of multi-dimensional polyline grid-drawings.
Submitted: April 2003.
Revised: March 2004.
Communicated by Giuseppe Liotta
article (PDF)