The maximum number of edges in a three-dimensional grid-drawing

Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

20 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)21-26
Number of pages6
JournalJournal of Graph Algorithms and Applications
Volume8
Issue number1
DOIs
Publication statusPublished - 2004
Externally publishedYes

Cite this