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, Konstanz, Germany , 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
ID Code:1198

Repository Staff Only: item control page


Akkerman, T., Buchheim, C., Jünger, M., Teske, D.: On the complexity of drawing trees nicely: Corrigendum. Acta Inf. 40(8), 603–607 (2004)

Aziza, S., Biedl, T.C.: Hexagonal grid drawings: Algorithms and lower bounds. In: Graph Drawing, pp. 18–24 (2004)

Bachmaier, C., Brandenburg, F.J., Brunner, W., Hofmeier, A., Matzeder, M., Unfried, T.: Tree drawings on the hexagonal grid. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 372–383. Springer, Heidelberg (2009)

Bachmaier, C., Brandenburg, F.J., Forster, M., Holleis, P., Raitner, M.: Gravisto: Graph visualization toolkit. In: Graph Drawing, pp. 502–503 (2004)

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

Chan, T.M., Goodrich, M.T., Kosaraju, 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)

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

Eades, P., Lin, T., Lin, X.: Minimum size h-v drawings. In: Advanced Visual Interfaces, pp. 386–394 (1992)

Eades, P., Whitesides, S.: The logic engine and the realization problem for nearest neighbor graphs. Theor. Comput. Sci. 169(1), 23–37 (1996)

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., 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)

Kaufmann, M., Wagner, D. (eds.): Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001)

Marriott, K., Stuckey, P.J.: NP-completeness of minimal width unordered tree layout. J. Graph Algorithms Appl. 8(2), 295–312 (2004)

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)

Supowit, K.J., Reingold, E.M.: The complexity of drawing trees nicely. Acta Inf. 18, 377–392 (1982)

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421–444 (1987)

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