Three-dimensional grid drawings with sub-quadratic volume

Vida Dujmovic, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-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 languageEnglish
Title of host publicationTowards a theory of geometric graphs
PublisherAmerican Mathematical Society
Pages55-66
Number of pages12
Volume342
DOIs
Publication statusPublished - 2004
Externally publishedYes

Publication series

NameContemp. Math.
PublisherAmer. Math. Soc., Providence, RI
  • 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 proceedingConference PaperResearchpeer-review

    6 Citations (Scopus)

Cite this