Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees

The planar slope number \,psn\,(G) psn ( G ) of a planar graph G is the minimum number of edge slopes in a planar straight-line drawing of G . It is known that \,psn\,(G) ∈ O(cΔ) psn ( G ) ∈ O ( c Δ ) for every planar graph G of maximum degree Δ Δ . This upper bound has been improved to O(Δ ⁵) O ( Δ 5 ) if G has treewidth three, and to O(Δ ) O ( Δ ) if G has treewidth two. In this paper we prove \,psn\,(G) ≤ max \4,Δ \ psn ( G ) ≤ max { 4 , Δ } when G is a Halin graph, and thus has treewidth three. Furthermore, we present the first polynomial upper bound on the planar slope number for a family of graphs having treewidth four. Namely we show that O(Δ ²) O ( Δ 2 ) slopes suffice for nested pseudotrees.