Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Straight-Line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio
(Extended Abstract)

Ashim GargContact Information and Adrian RusuContact Information

(6)  Department of Computer Science and Engineering, University at Buffalo, NY 14260 Buffalo
Abstract
Trees are usually drawn planar, i.e. without any crossings. In this paper, we investigate the area requirement of (non-upward) planar straight-line grid drawings of binary trees. Let T be a binary tree with n nodes. We show that T admits a planar straight-line grid drawing with area O(n) and with any pre-specified aspect ratio in the range [1, n α ], where α is a constant such that 0 ≤ α < 1. We also show that such a drawing can be constructed in O(n log n) time.
Research supported by NSF CAREER Award IIS-9985136and NSF CISE Research Infrastructure Award No. 0101244.

Contact Information Ashim Garg
Email: agarg@cse.buffalo.edu

Contact Information Adrian Rusu
Email: adirusu@cse.buffalo.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb23
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)