Three-dimensional 1-bend graph drawings

Pat Morin; David R. Wood

doi:10.7155/jgaa.00095

Three-dimensional 1-bend graph drawings

Pat Morin, David R. Wood

Research output: Contribution to journal › Article › Research › peer-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 language	English
Pages (from-to)	357-366
Number of pages	10
Journal	Journal of Graph Algorithms and Applications
Volume	8
Issue number	3
DOIs	https://doi.org/10.7155/jgaa.00095
Publication status	Published - 2004
Externally published	Yes

Access to Document

10.7155/jgaa.00095

Cite this

@article{2b902cbd892c4442a6e156e5f94bfae8,

title = "Three-dimensional 1-bend graph drawings",

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

author = "Pat Morin and Wood, {David R.}",

year = "2004",

doi = "10.7155/jgaa.00095",

language = "English",

volume = "8",

pages = "357--366",

journal = "Journal of Graph Algorithms and Applications",

issn = "1526-1719",

publisher = "Brown University",

number = "3",

}

TY - JOUR

T1 - Three-dimensional 1-bend graph drawings

AU - Morin, Pat

AU - Wood, David R.

PY - 2004

Y1 - 2004

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

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

U2 - 10.7155/jgaa.00095

DO - 10.7155/jgaa.00095

M3 - Article

VL - 8

SP - 357

EP - 366

JO - Journal of Graph Algorithms and Applications

JF - Journal of Graph Algorithms and Applications

SN - 1526-1719

IS - 3

ER -