Tree Drawings on the Hexagonal Grid

Bachmaier, Christian and Brandenburg, Franz J. and Brunner, Wolfgang and Hofmeier, Andreas and Matzeder, Marco and Unfried, Thomas (2009) Tree Drawings on the Hexagonal Grid. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008 , pp. 372-383(Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_36).

Full text not available from this repository.

Abstract

We consider straight-line drawings of trees on a hexagonal grid. The hexagonal grid is an extension of the common grid with inner nodes of degree six. We restrict the number of directions used for the edges from each node to its children from one to five, and to five patterns: straight, Y , ψ , X , and full. The ψ - drawings generalize hv - or strictly upward drawings to ternary trees. We show that complete ternary trees have a ψ-drawing on a square of size O(n1.262 ) and general ternary trees can be drawn within O(n1.631 ) area. Both bounds are optimal. Sub- quadratic bounds are also obtained for X- pattern drawings of complete tetra trees, and for full- pattern drawings of complete penta trees, which are 4- ary and 5- ary trees. These results parallel and complement the ones of Frati [8] for straight- line orthogonal drawings of ternary trees. Moreover, we provide an algorithm for compacted straight- line drawings of penta trees on the hexagonal grid, such that the direction of the edges from a node to its children is given by our patterns and these edges have the same length. However, drawing trees on a hexagonal grid within a prescribed area or with unit length edges is N P -hard.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-642-00219-9_36
Classifications:	M Methods > M.900 Tree
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/925

Actions (login required)

View Item