Really straight graph drawings

Vida Dujmović, Matthew Suderman, David R. Wood

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

13 Citations (Scopus)

Abstract

We study straight-line drawings of graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most 5n/2 segments and at most 2n slopes, and that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). Drawings of non-planar graphs with few slopes are also considered. For example, it is proved that graphs of bounded degree and bounded treewidth have drawings with script O sign(log n) slopes.

Original languageEnglish
Title of host publicationGraph Drawing
Subtitle of host publication12th International Symposium, GD 2004 New York, NY, USA, September 29-October 2, 2004 Revised Selected Papers
EditorsJános Pach
Place of PublicationBerlin Germany
PublisherSpringer
Pages122-132
Number of pages11
ISBN (Print)3540245286
DOIs
Publication statusPublished - 1 Dec 2004
Externally publishedYes
EventGraph Drawing 2004 - New York, United States of America
Duration: 29 Sep 20042 Oct 2004
Conference number: 12th
https://link.springer.com/book/10.1007/b105810 (Proceedings)

Publication series

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

Conference

ConferenceGraph Drawing 2004
Abbreviated titleGD 2004
CountryUnited States of America
CityNew York
Period29/09/042/10/04
Internet address

Cite this