Skip to main content
Article
The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
Graphs and Combinatorics (2013)
  • Vít Jelínek, Charles University
  • Eva Jelínková, Charles University
  • Jan Kratochvíl, Charles University
  • Bernard Lidicky, Charles University
  • Marek Tesař, Charles University
  • Tomáš Vyskočil, Charles University
Abstract
It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree Δ. We show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most O(Δ5). In particular, we answer the question of Dujmović et al. (Comput Geom 38(3):194–212, 2007) whether there is a function f such that plane maximal outerplanar graphs can be drawn using at most f(Δ) slopes.
Keywords
  • Graph drawing,
  • Planar graphs,
  • Slopes,
  • Planar slope number
Publication Date
July, 2013
DOI
10.1007/s00373-012-1157-z
Publisher Statement
The final publication is available at Springer via https://doi.org/10.1007/s00373-012-1157-z.Jelínek, Vít, Eva Jelínková, Jan Kratochvíl, Bernard Lidický, Marek Tesař, and Tomáš Vyskočil. "The planar slope number of planar partial 3-trees of bounded degree." Graphs and Combinatorics 29, no. 4 (2013): 981-1005. doi: 10.1007/s00373-012-1157-z. Posted with permission

Copyright 2012 Springer
Citation Information
Vít Jelínek, Eva Jelínková, Jan Kratochvíl, Bernard Lidicky, et al.. "The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree" Graphs and Combinatorics Vol. 29 Iss. 4 (2013) p. 981 - 1005
Available at: http://works.bepress.com/bernard-lidicky/17/