Path-width and three-dimensional straight-line grid drawings of graphs

Vida Dujmović, Pat Morin, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingChapter (Report)Researchpeer-review

18 Citations (Scopus)

Abstract

We prove that every n-vertex graph G with path-width pw(G) has a three-dimensional straight-line grid drawing with O(pw(G) 2 ·n) volume. Thus for graphs with bounded path-width the volume is O(n), and it follows that for graphs with bounded tree-width, such as series-parallel graphs, the volume is O(n log 2 n). No better bound than O(n 2) was previously known for drawings of series-parallel graphs. For planar graphs we obtain three-dimensional drawings with O(n 2) volume and O(√n) aspect ratio, whereas all previous constructions with O(n 2) volume have θ(n) aspect ratio.

Original languageEnglish
Title of host publicationGraph Drawing - 10th International Symposium, GD 2002, Revised Papers
PublisherSpringer
Pages42-53
Number of pages12
Volume2528 LNCS
ISBN (Print)3540001581, 9783540001584
DOIs
Publication statusPublished - 2002
Externally publishedYes
EventGraph Drawing 2002 - Irvine, United States of America
Duration: 26 Aug 200228 Aug 2002
Conference number: 10th
https://link.springer.com/book/10.1007/3-540-36151-0 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2528 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceGraph Drawing 2002
Abbreviated titleGD 2002
CountryUnited States of America
CityIrvine
Period26/08/0228/08/02
Internet address

Cite this