We study the width requirements of LR-drawings of n-node ordered rooted binary trees; these are the drawings produced by a family of tree drawing algorithms introduced by Chan, who showed how to construct LR-drawings with width O(n^0.48 ). We prove that LR-drawings with minimum width can be constructed in O(n^1.48) time. Further, we show an infinite family of n-node ordered rooted binary trees requiring Omega(n^0.418 ) width in any LR-drawing and we present the results of an experimental evaluation that allowed us to determine the minimum width of all the ordered rooted binary trees with up to 455 nodes. We also show that, if n-node ordered rooted binary trees have LR-drawings with f (n) width, for any function f(n), then n-vertex outerplanar graphs have outerplanar straight-line drawings in O ( f ( n )) area. Finally, we prove that every n-vertex outerplanar graph has an outerplanar straight-line drawing in O(n 2^sqrt(2 log_2 n) sqrt(log n)) area.

Frati, F., Patrignani, M., Roselli, V. (2020). LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 107, 28-53 [10.1016/j.jcss.2019.08.001].

LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs

Frati, Fabrizio;Patrignani, Maurizio;Roselli, Vincenzo
2020-01-01

Abstract

We study the width requirements of LR-drawings of n-node ordered rooted binary trees; these are the drawings produced by a family of tree drawing algorithms introduced by Chan, who showed how to construct LR-drawings with width O(n^0.48 ). We prove that LR-drawings with minimum width can be constructed in O(n^1.48) time. Further, we show an infinite family of n-node ordered rooted binary trees requiring Omega(n^0.418 ) width in any LR-drawing and we present the results of an experimental evaluation that allowed us to determine the minimum width of all the ordered rooted binary trees with up to 455 nodes. We also show that, if n-node ordered rooted binary trees have LR-drawings with f (n) width, for any function f(n), then n-vertex outerplanar graphs have outerplanar straight-line drawings in O ( f ( n )) area. Finally, we prove that every n-vertex outerplanar graph has an outerplanar straight-line drawing in O(n 2^sqrt(2 log_2 n) sqrt(log n)) area.
2020
Frati, F., Patrignani, M., Roselli, V. (2020). LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 107, 28-53 [10.1016/j.jcss.2019.08.001].
File in questo prodotto:
File Dimensione Formato  
Frati-LR-Drawings of Ordered Rooted Binary Trees (submitted to JCSS).pdf

accesso aperto

Descrizione: Preprint submitted to editor
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 1.95 MB
Formato Adobe PDF
1.95 MB Adobe PDF Visualizza/Apri

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/360767
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 2
social impact