2021/05/17 by Steven Chaplick, Giordano Da Lozzo, Chaplick, Steven +7 · 1 citation
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2105.08124
openalex publication_date 2021/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The 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) ∈ O(cΔ) for every planar graph G of maximum degree Δ. This upper bound has been improved to O(Δ5) if G has treewidth three, and to O(Δ) if G has treewidth two. In this paper we prove 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(Δ2) slopes suffice for nested pseudotrees.