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.
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].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/391784
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 0
social impact