Three-dimensional grid drawings with sub-quadratic volume

Vida Dujmović, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

6 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(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 publicationGraph Drawing
Subtitle of host publication11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers
EditorsGiuseppe Liotta
Place of PublicationBerlin Germany
PublisherSpringer
Pages190-201
Number of pages12
ISBN (Print)3540208313
DOIs
Publication statusPublished - 2004
Externally publishedYes
EventGraph Drawing 2003 - Perugia, Italy
Duration: 21 Sep 200324 Sep 2003
Conference number: 11th
https://link.springer.com/book/10.1007/b94919 (Proceedings)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2912
ISSN (Print)0302-9743

Conference

ConferenceGraph Drawing 2003
Abbreviated titleGD 2003
CountryItaly
CityPerugia
Period21/09/0324/09/03
Internet address

Cite this