Drawing Unordered Trees on k-Grids

Abstract

We present almost linear area bounds for drawing trees on the octagonal grid. For complete 7-ary trees we establish an upper and lower bound of Θ(n^1.129) and for complete ternary trees the bounds of O(n^1.048) and Θ(n), where the latter needs edge bends. For arbitrary ternary trees we obtain an upper bound of O(n log log n) with bends and good aspect ratio by applying the recursive winding technique. We explore the unit edge length and area complexity of drawing unordered trees on k-grids with k∈{4,6,8} and generalize the NP-hardness results of the orthogonal grid to the octagonal and hexagonal grids.