Upward Octagonal Drawings of Ternary Trees

graph drawing;ternary trees;octagonal;tree drawing

Lee, Seunghee

University of Waterloo

关键词: graph drawing;    ternary trees;    octagonal;    tree drawing;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/10832/1/Lee_Seunghee.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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(n^{0.68})$ width. (This bound can be improved to $O(n^{0.631})$ width in the so-called HVA-model.) For ideal octagonal grid drawings of complete $n$-node ternary trees, we provide an $Omega(n^{0.411})$ width lower bound.