A NOTE ON MINIMUM-AREA UPWARD DRAWING OF COMPLETE AND FIBONACCI TREES

Authors
TREVISAN L
Citation
L. Trevisan, A NOTE ON MINIMUM-AREA UPWARD DRAWING OF COMPLETE AND FIBONACCI TREES, Information processing letters, 57(5), 1996, pp. 231-236
Citations number
12
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
57
Issue
5
Year of publication
1996
Pages
231 - 236
Database
ISI
SICI code
0020-0190(1996)57:5<231:ANOMUD>2.0.ZU;2-#
Abstract
We study the area requirements for strictly-upward straight-line grid drawings of complete and Fibonacci trees. We prove that a complete tre e with n nodes can be drawn in n + O(log n root n) area, and a Fibonac ci tree with n nodes can be drawn in 1.17n + O(log n root n) area.