Back to search

University of Waterloo

Upward Octagonal Drawings of Ternary Trees

Abstract

dc:description.abstract

We 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 × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/10832

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lee, Seunghee. Upward Octagonal Drawings of Ternary Trees. University of Waterloo, 2016. http://hdl.handle.net/10012/10832