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.
Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees
Di Giacomo E.;Liotta G.;Montecchiani F.
2021
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.