Abstract
We consider three-dimensional grid-drawings of graphs with at most one bend per edge. Under the additional requirement that the vertices be collinear, we prove that the minimum volume of such a drawing is θ(cn), where n is the number of vertices and c is the cutwidth of the graph. We then prove that every graph has a three-dimensional grid-drawing with ο(n3/log 2 n) volume and one bend per οdge. The best previous bound was ο(n3).
Original language | English |
---|---|
Pages (from-to) | 357-366 |
Number of pages | 10 |
Journal | Journal of Graph Algorithms and Applications |
Volume | 8 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2004 |
Externally published | Yes |