Drawing Ordered (k - 1)-Ary Trees on k-Grids

Brunner, Wolfgang and Matzeder, Marco (2011) Drawing Ordered (k - 1)-Ary Trees on k-Grids. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010 , pp. 105-116(Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_10).

Full text not available from this repository.


We explore the complexity of drawing ordered (k - 1)-ary trees on grids with k directions for k E and within a given area. This includes, e.g., ternary trees drawn on the orthogonal grid. For aesthetically pleasing tree drawings on these grids, we additionally present various restrictions similar to the common hierarchical case. First, we generalize the NP-hardness of minimal width in hierarchical drawings of ordered trees to (k - 1)-ary trees on k-grids and then we generalize the Reingold and Tilford algorithm to k-grids.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-18469-7_10
Classifications: M Methods > M.900 Tree
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1198

Actions (login required)

View Item View Item