Three-dimensional grid drawings with sub-quadratic volume

Vida Dujmovic; David R. Wood

doi:10.1090/conm/342/06130

Three-dimensional grid drawings with sub-quadratic volume

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

Abstract

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise non-crossing. A O(n 3/2) volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was O(n2). These results (partially) solve open problems due to Pach, Thiele, and Tóth [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001].

Original language	English
Title of host publication	Towards a theory of geometric graphs
Publisher	American Mathematical Society
Pages	55-66
Number of pages	12
Volume	342
DOIs	https://doi.org/10.1090/conm/342/06130
Publication status	Published - 2004
Externally published	Yes

Publication series

Name	Contemp. Math.
Publisher	Amer. Math. Soc., Providence, RI

Access to Document

10.1090/conm/342/06130

1 Conference Paper

Three-dimensional grid drawings with sub-quadratic volume
Dujmović, V. & Wood, D. R., 2004, Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers. Liotta, G. (ed.). Berlin Germany: Springer, p. 190-201 12 p. (Lecture Notes in Computer Science; vol. 2912).
Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

7 Citations (Scopus)

Cite this

@inbook{89cdeaaa76284c2e982c273390d37c05,

title = "Three-dimensional grid drawings with sub-quadratic volume",

abstract = "A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise non-crossing. A O(n 3/2) volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was O(n2). These results (partially) solve open problems due to Pach, Thiele, and T{\'o}th [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001]. ",

author = "Vida Dujmovic and Wood, {David R.}",

year = "2004",

doi = "10.1090/conm/342/06130",

language = "English",

volume = "342",

series = "Contemp. Math.",

publisher = "American Mathematical Society",

pages = "55--66",

booktitle = "Towards a theory of geometric graphs",

address = "United States of America",

}

TY - CHAP

T1 - Three-dimensional grid drawings with sub-quadratic volume

AU - Dujmovic, Vida

AU - Wood, David R.

PY - 2004

Y1 - 2004

N2 - A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise non-crossing. A O(n 3/2) volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was O(n2). These results (partially) solve open problems due to Pach, Thiele, and Tóth [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001].

AB - A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise non-crossing. A O(n 3/2) volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was O(n2). These results (partially) solve open problems due to Pach, Thiele, and Tóth [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001].

U2 - 10.1090/conm/342/06130

DO - 10.1090/conm/342/06130

M3 - Chapter (Book)

VL - 342

T3 - Contemp. Math.

SP - 55

EP - 66

BT - Towards a theory of geometric graphs

PB - American Mathematical Society

ER -