We prove that every n-node ternary tree has a planar straight-line orthogonal drawing in O(n^1.576) area, improving upon the previously best known O(n^1.631) bound. Further, we present an upper bound, the outcomes of an experimental evaluation, and a conjecture on the area requirements of planar straight-line orthogonal drawings of complete ternary trees.
Covella, B., Frati, F., Patrignani, M. (2018). On the area requirements of straight-line orthogonal drawings of ternary trees. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.128-140). Springer Verlag [10.1007/978-3-319-94667-2_11].
On the area requirements of straight-line orthogonal drawings of ternary trees
COVELLA, BARBARA;Frati, Fabrizio
;Patrignani, Maurizio
2018-01-01
Abstract
We prove that every n-node ternary tree has a planar straight-line orthogonal drawing in O(n^1.576) area, improving upon the previously best known O(n^1.631) bound. Further, we present an upper bound, the outcomes of an experimental evaluation, and a conjecture on the area requirements of planar straight-line orthogonal drawings of complete ternary trees.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
