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