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

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

doi:10.7155/jgaa.00079

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

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

Research output: Contribution to journal › Article › Research › peer-review

21 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 language	English
Pages (from-to)	21-26
Number of pages	6
Journal	Journal of Graph Algorithms and Applications
Volume	8
Issue number	1
DOIs	https://doi.org/10.7155/jgaa.00079
Publication status	Published - 2004
Externally published	Yes

Access to Document

10.7155/jgaa.00079

Cite this

@article{579b33f939cc4f8ea03ff1f68c881fae,

title = "The maximum number of edges in a three-dimensional grid-drawing",

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.",

author = "Prosenjit Bose and Jurek Czyzowicz and Pat Morin and Wood, {David R.}",

year = "2004",

doi = "10.7155/jgaa.00079",

language = "English",

volume = "8",

pages = "21--26",

journal = "Journal of Graph Algorithms and Applications",

issn = "1526-1719",

publisher = "Brown University",

number = "1",

}

TY - JOUR

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

AU - Bose, Prosenjit

AU - Czyzowicz, Jurek

AU - Morin, Pat

AU - Wood, David R.

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

U2 - 10.7155/jgaa.00079

DO - 10.7155/jgaa.00079

M3 - Article

SN - 1526-1719

VL - 8

SP - 21

EP - 26

JO - Journal of Graph Algorithms and Applications

JF - Journal of Graph Algorithms and Applications

IS - 1

ER -