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. Journal articles
  4. Drawing Planar Graphs Of Bounded Degree With Few Slopes
 
research article

Drawing Planar Graphs Of Bounded Degree With Few Slopes

Keszegh, Balazs  
•
Pach, Janos  
•
Palvoelgyi, Doemoetoer  
2013
SIAM Journal on Discrete Mathematics

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. Every other planar graph requires exactly [d/2] slopes.

  • Details
  • Metrics
Type
research article
DOI
10.1137/100815001
Web of Science ID

WOS:000321042800035

Author(s)
Keszegh, Balazs  
Pach, Janos  
Palvoelgyi, Doemoetoer  
Date Issued

2013

Publisher

SIAM Publications

Published in
SIAM Journal on Discrete Mathematics
Volume

27

Issue

2

Start page

1171

End page

1183

Subjects

graph drawing

•

slope number

•

planar graphs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
October 1, 2013
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/95934
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