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, Heraklion, Crete, Greece , 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
ID Code:925

Repository Staff Only: item control page

References

Bhatt, S.N., Cosmadakis, S.S.: The complexity of minimizing wire lengths in VLSI layouts. Inf. Process. Lett. 25(4), 263-267 (1987)

Bloesch, A.: Aestetic layout of generalized trees. Softw. Pract. Exper. 23(8), 817- 827 (1993)

Chan, T.M., Goodrich, M.T., Kosara ju, S.R., Tamassia, R.: Optimizing area and aspect ratio in straight-line orthogonal tree drawings. Comput. Geom. Theory Appl. 23(2), 153-162 (2002)

Crescenzi, P., Di Battista, G., Piperno, A.: A note on optimal area algorithms for upward drawings of binary trees. Comput. Geom. Theory Appl. 2, 187- 200 (1992)

Dolev, D., Trickey, H.W.: On linear area embedding of planar graphs. Tech. Rep. STAN-CS-81-876, Stanford University, Stanford, CA, USA (1981)

Dujmović, V., Suderman, M., Wood, D.R.: Really straight graph drawings. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 122-132. Springer, Heidelberg (2005)

Eades, P.: Drawing free trees. Bulletin of the Institute of Combinatorics and its Applications 5, 10-36 (1992)

Frati, F.: Straight-line orthogonal drawings of binary and ternary trees. In: Hong, S.H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 76-87. Springer, Heidelberg (2008)

Garg, A., Goodrich, M.T., Tamassia, R.: Planar upward tree drawings with optimal area. Int. J. Comput. Geometry Appl. 6(3), 333-356 (1996)

Garg, A., Rusu, A.: Straight-line drawings of binary trees with linear area and arbitrary aspect ratio. J. Graph Algo. App. 8(2), 135-160 (2004)

Kant, G.: Hexagonal grid drawings. In: Mulkers A. (ed.) Live Data Structures in Logic Programs. LNCS, vol. 675, pp. 263-276. Springer, Heidelberg (1993)

Knuth, D.E.: The Art of Computer Programming, vol.1. Addison-Wesley (1968)

Reingold, E.M., Tilford, J.S.: Tidier drawing of trees. IEEE Trans. Software Eng. 7(2), 223-228 (1981)

Shin, C.S., Kim, S.K., Chwa, K.Y.: Area-efficient algorithms for straight-line tree drawings. Comput. Geom. Theory Appl. 15(4), 175-202 (2000)

Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Computers 30(2), 135-140 (1981)

Walker, J.Q.W.: A node-positioning algorithm for general trees. Softw. Pract. Exper. 20(7), 685-705 (1990)