Three-dimensional grid drawings with sub-quadratic volume

Vida Dujmović; David R. Wood

doi:10.1007/978-3-540-24595-7_18

Three-dimensional grid drawings with sub-quadratic volume

Vida Dujmović, David R. Wood

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

7 Citations (Scopus)

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(n²). 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	Graph Drawing
Subtitle of host publication	11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers
Editors	Giuseppe Liotta
Place of Publication	Berlin Germany
Publisher	Springer
Pages	190-201
Number of pages	12
ISBN (Print)	3540208313
DOIs	https://doi.org/10.1007/978-3-540-24595-7_18
Publication status	Published - 2004
Externally published	Yes
Event	Graph Drawing 2003 - Perugia, Italy Duration: 21 Sept 2003 → 24 Sept 2003 Conference number: 11th https://link.springer.com/book/10.1007/b94919 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2912
ISSN (Print)	0302-9743

Conference

Conference	Graph Drawing 2003
Abbreviated title	GD 2003
Country/Territory	Italy
City	Perugia
Period	21/09/03 → 24/09/03
Internet address	https://link.springer.com/book/10.1007/b94919 (Proceedings)

Access to Document

10.1007/978-3-540-24595-7_18

Cite this

@inproceedings{0f8bb17efdec44a7b26faf77f4581b67,

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 Dujmovi{\'c} and Wood, {David R.}",

year = "2004",

doi = "10.1007/978-3-540-24595-7_18",

language = "English",

isbn = "3540208313",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "190--201",

editor = "Giuseppe Liotta",

booktitle = "Graph Drawing",

note = "Graph Drawing 2003, GD 2003 ; Conference date: 21-09-2003 Through 24-09-2003",

url = "https://link.springer.com/book/10.1007/b94919",

}

Dujmović, V & Wood, DR 2004, Three-dimensional grid drawings with sub-quadratic volume. in G Liotta (ed.), Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers. Lecture Notes in Computer Science, vol. 2912, Springer, Berlin Germany, pp. 190-201, Graph Drawing 2003, Perugia, Italy, 21/09/03. https://doi.org/10.1007/978-3-540-24595-7_18

Three-dimensional grid drawings with sub-quadratic volume. / Dujmović, Vida; Wood, David R.
Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers. ed. / Giuseppe Liotta. Berlin Germany: Springer, 2004. p. 190-201 (Lecture Notes in Computer Science; Vol. 2912).

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

TY - GEN

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

AU - Dujmović, Vida

AU - Wood, David R.

N1 - Conference code: 11th

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].

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

U2 - 10.1007/978-3-540-24595-7_18

DO - 10.1007/978-3-540-24595-7_18

M3 - Conference Paper

SN - 3540208313

T3 - Lecture Notes in Computer Science

SP - 190

EP - 201

BT - Graph Drawing

A2 - Liotta, Giuseppe

PB - Springer

CY - Berlin Germany

T2 - Graph Drawing 2003

Y2 - 21 September 2003 through 24 September 2003

ER -

Three-dimensional grid drawings with sub-quadratic volume

Abstract

Publication series

Conference

Access to Document

Other files and links

Research output

Three-dimensional grid drawings with sub-quadratic volume

Cite this