The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree

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 $\Delta$. We show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most $O({\Delta }^5)$. In particular, we answer the question of Dujmović et al. [Computational Geometry 38 (3), pp. 194--212 (2007)] whether there is a function $f$ such that plane maximal outerplanar graphs can be drawn using at most $f(\Delta )$ slopes.

34 pages, 18 figures, old version was at Graph Drawing 2009

References in corpus (4)

• Drawings of Planar Graphs with Few Slopes and Segments
• Graph Drawings with Few Slopes
• A note on planar partial 3-trees
• Drawing cubic graphs with the four basic slopes

Cited by in corpus (5)

• Outerplanar graph drawings with few slopes
• A note on planar partial 3-trees
• Decomposition of Geometric Set Systems and Graphs
• 1-bend Upward Planar Drawings of SP-digraphs
• Upward planar drawings with two slopes