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

摘要

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 series-parallel graph of maximum degree three is three.We also show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most 2~(O(△)).In particular, we answer the question of Dujmovic et al.[Computational Geometry 38 (3), pp.194-212 (2007)] whether there is a function / such that plane maximal outerplanar graphs can be drawn using at most f(△) slopes.