Drawing Unordered Trees on k-Grids
Christian Bachmaier, Marco Matzeder · Journal of Graph Algorithms and Applications · 2013
Abstract. We present almost linear area bounds for drawing complete trees on the octagonal grid. For 7-ary trees we establish an upper and lower bound of Θ(n 1.129) and for ternary trees the bounds of O(n 1.048) and Θ(n), where the latter needs edge bends. We explore the unit edge length and area complexity of drawing unordered trees on k-grids with k ∈ {4, 6, 8} and generalize the N P-hardness results of the orthogonal and hexagonal grid to the octagonal grid. 1