Three-dimensional 1-bend graph drawings

Pat Morin; David R. Wood

doi:10.1142/9789812773289_0018

Three-dimensional 1-bend graph drawings

Research output: Chapter in Book/Report/Conference proceeding › Chapter (Book) › Research › peer-review

Abstract

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 풪(n³/log² n) volume and one bend per edge. The best previous bound was 풪(n³).

Original language	English
Title of host publication	Graph Algorithms and Applications 5
Publisher	World Scientific Publishing
Pages	357-367
Number of pages	11
ISBN (Electronic)	9789812773289
ISBN (Print)	981256845X, 9789812568458
DOIs	https://doi.org/10.1142/9789812773289_0018
Publication status	Published - 1 Jan 2006
Externally published	Yes

Access to Document

10.1142/9789812773289_0018

Cite this

@inbook{a54da41e9226432d848884a79d8ba263,

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

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

year = "2006",

month = jan,

day = "1",

doi = "10.1142/9789812773289\_0018",

language = "English",

isbn = "981256845X",

pages = "357--367",

booktitle = "Graph Algorithms and Applications 5",

publisher = "World Scientific Publishing",

address = "Singapore",

}

TY - CHAP

T1 - Three-dimensional 1-bend graph drawings

AU - Morin, Pat

AU - Wood, David R.

PY - 2006/1/1

Y1 - 2006/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=84968754683&partnerID=8YFLogxK

U2 - 10.1142/9789812773289_0018

DO - 10.1142/9789812773289_0018

M3 - Chapter (Book)

AN - SCOPUS:84968754683

SN - 981256845X

SN - 9789812568458

SP - 357

EP - 367

BT - Graph Algorithms and Applications 5

PB - World Scientific Publishing

ER -

Three-dimensional 1-bend graph drawings

Abstract

Access to Document

Other files and links

Cite this