Abstract
dc:description.abstractWe explore ways to embed a ternary tree in an integer coordinate grid such that the width of the drawing is minimized. We provide upper and lower bounds on the width requirement of planar, straight-line, upward, order-preserving drawings of ternary trees in an octagonal grid. We present a linear-time algorithm for constructing such octagonal grid drawings of any $n$-node ternary tree with O(n0.68) width. (This bound can be improved to O(n0.631) width in the so-called HVA-model.) For ideal octagonal grid drawings of complete $n$-node ternary trees, we provide an \Omega(n0.411) width lower bound.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2016
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Lee, Seunghee
- Advisors dc:contributor.advisor
-
- Chan, Timothy
- Biedl, Therese
Subjects
dc:subject × 4Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/10832