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 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) ∈ Θ(Δ) 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.
Chaplick, S., Da Lozzo, G., Di Giacomo, E., Liotta, G., Montecchiani, F. (2021). Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.271-285). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-83508-8_20].
Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees
Da Lozzo G.
;
2021-01-01
Abstract
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 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) ∈ Θ(Δ) 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
