Drawings of planar graphs with few slopes and segments

Vida Dujmovic; David Eppstein; Matthew Suderman; David R. Wood

doi:10.1016/j.comgeo.2006.09.002

Drawings of planar graphs with few slopes and segments

Vida Dujmovic
, David Eppstein
, Matthew Suderman
, David R. Wood

Research output: Contribution to journal › Article › Research › peer-review

73 Citations (Scopus)

Abstract

We study straight-line drawings of planar 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 52n segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). In a companion paper, drawings of non-planar graphs with few slopes are also considered.

Original language	English
Pages (from-to)	194-212
Number of pages	19
Journal	Computational Geometry: Theory and Applications
Volume	38
Issue number	3
DOIs	https://doi.org/10.1016/j.comgeo.2006.09.002
Publication status	Published - 2007
Externally published	Yes

Access to Document

10.1016/j.comgeo.2006.09.002

Cite this

@article{611bb0b896c94e1ba36da42742a1c974,

title = "Drawings of planar graphs with few slopes and segments",

abstract = "We study straight-line drawings of planar 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 52n segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). In a companion paper, drawings of non-planar graphs with few slopes are also considered. ",

author = "Vida Dujmovic and David Eppstein and Matthew Suderman and Wood, \{David R.\}",

year = "2007",

doi = "10.1016/j.comgeo.2006.09.002",

language = "English",

volume = "38",

pages = "194--212",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Drawings of planar graphs with few slopes and segments

AU - Dujmovic, Vida

AU - Eppstein, David

AU - Suderman, Matthew

AU - Wood, David R.

PY - 2007

Y1 - 2007

N2 - We study straight-line drawings of planar 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 52n segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). In a companion paper, drawings of non-planar graphs with few slopes are also considered.

AB - We study straight-line drawings of planar 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 52n segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). In a companion paper, drawings of non-planar graphs with few slopes are also considered.

U2 - 10.1016/j.comgeo.2006.09.002

DO - 10.1016/j.comgeo.2006.09.002

M3 - Article

SN - 0925-7721

VL - 38

SP - 194

EP - 212

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 3

ER -