Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00079 The Maximum Number of Edges in a Three-Dimensional Grid-Drawing Prosenjit Bose , Jurek Czyzowicz , Pat Morin , and David R. Wood 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 |
| Journal of Graph Algorithms and Applications |