Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees
2021
The planar slope number \(\mathrm {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 \(\mathrm {psn}(G) \in O(c^{\varDelta })\) for every planar graph G of degree \(\varDelta \). This upper bound has been improved to \(O(\varDelta ^5)\) if G has treewidth three, and to \(O(\varDelta )\) if G has treewidth two. In this paper we prove \(\mathrm {psn}(G) \in \varTheta (\varDelta )\) 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(\varDelta ^2)\) slopes suffice for nested pseudotrees.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
23
References
0
Citations
NaN
KQI