Three-dimensional 1-bend graph drawings

Pat Morin, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review


We consider three-dimensional grid-drawings of graphs with at most one bend per edge. Under the additional requirement that the vertices be colhnear, 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/log2 n) volume and one bend per edge. The best previous bound was 풪(n3).

Original languageEnglish
Title of host publicationGraph Algorithms and Applications 5
PublisherWorld Scientific Publishing
Number of pages11
ISBN (Electronic)9789812773289
ISBN (Print)981256845X, 9789812568458
Publication statusPublished - 1 Jan 2006
Externally publishedYes

Cite this