1. Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees.
- Author
-
Chaplick, Steven, Da Lozzo, Giordano, Di Giacomo, Emilio, Liotta, Giuseppe, and Montecchiani, Fabrizio
- Abstract
The
planar slope number psn(G)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\,\textrm{psn}\,}}(G)$$\end{document} of a planar graphG is the minimum number of edge slopes in a planar straight-line drawing ofG . It is known that psn(G)∈O(cΔ)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\,\textrm{psn}\,}}(G) \in O(c^{\Delta })$$\end{document} for every planar graphG of maximum degree Δ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\Delta $$\end{document}. This upper bound has been improved to O(Δ5)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(\Delta ^5)$$\end{document} ifG has treewidth three, and to O(Δ)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(\Delta )$$\end{document} ifG has treewidth two. In this paper we prove psn(G)≤max{4,Δ}\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\,\textrm{psn}\,}}(G) \le \max \{4,\Delta \}$$\end{document} whenG 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)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(\Delta ^2)$$\end{document} slopes suffice for nested pseudotrees. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF