Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Drawing planar graphs of bounded degree with few slopes
 
conference paper

Drawing planar graphs of bounded degree with few slopes

Keszegh, Balázs  
•
Pach, János  
•
Palvoelgyi, Doemoetoer  
2011
Graph Drawing. GD 2010
18th International Symposium on Graph Drawing

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different slopes. If we allow the edges to be represented by polygonal paths with one bend. then 2d slopes suffice. Allowing two bends per edge, every planar graph with maximum degree d >= 3 can be drawn using segments of at most [d/2] different slopes. There is only one exception: the graph formed by the edges of an octahedron is 4-regular, yet it requires 3 slopes. These bounds cannot be improved.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-642-18469-7_27
Web of Science ID

WOS:000297038000027

Author(s)
Keszegh, Balázs  
Pach, János  
Palvoelgyi, Doemoetoer  
Date Issued

2011

Publisher

Springer-Verlag

Publisher place

New York

Published in
Graph Drawing. GD 2010
Series title/Series vol.

Lecture Notes in Computer Science

Start page

293

End page

304

Subjects

Graph drawing

•

Slope number

•

Planar graphs

•

Cubic Graphs

•

Number

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Event nameEvent placeEvent date
18th International Symposium on Graph Drawing

Konstanz, Germany

September 21-24, 2010

Available on Infoscience
December 12, 2011
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/73115
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés