Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees

Abstract

The $\text{planar slope number}$ $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)\in O(c^{\hat{I}}”)$ for every planar graph $G$ of maximum degree $\hat{I}”$. This upper bound has been improved to $O(\hat{I}{”}^5)$ if $G$ has treewidth three, and to $O(\hat{I}”)$ if $G$ has treewidth two. In this paper we prove $psn(G)\le \max \{4,\hat{I}”\}$ 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(\hat{I}{”}^2)$ slopes suffice for nested pseudotrees.

Extended version of "Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees" appeared in the Proceedings of the 17th Algorithms and Data Structures Symposium (WADS 2021)