Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees
Steven Chaplick, Giordano Da Lozzo, Emilio Di Giacomo, Giuseppe Liotta, Fabrizio Montecchiani · Algorithmica · 2024
Abstract The planar slope number $${{\,\textrm{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 $${{\,\textrm{psn}\,}}(G) \in O(c^{\Delta })$$ psn ( G ) ∈ O ( c Δ ) for every planar graph G of maximum degree $$\Delta $$ Δ . This upper bound has been improved to $$O(\Delta ^5)$$ O ( Δ 5 ) if G has treewidth three, and to $$O(\Delta )$$ O ( Δ ) if G has treewidth two. In this paper we prove $${{\,\textrm{psn}\,}}(G) \le \max \{4,\Delta \}$$ 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(\Delta ^2)$$ O ( Δ 2 ) slopes suffice for nested pseudotrees.