Three-dimensional 1-bend graph drawings

Pat Morin, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)

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 languageEnglish
Pages (from-to)357-366
Number of pages10
JournalJournal of Graph Algorithms and Applications
Volume8
Issue number3
DOIs
Publication statusPublished - 2004
Externally publishedYes

Cite this