Schematisation of Tree Drawings

Gudmundsson, Joachim and Van Kreveld, Marc and Merrick, Damian (2007) Schematisation of Tree Drawings. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 66-76 (Official URL:

Full text not available from this repository.


Given a tree T spanning a set of points S in the plane, we study the problem of drawing T using only line segments aligned with a fixed set of directions C. The vertices in the drawing must lie within a given distance r of each original point p in S, and an objective function counting the number of bends must be minimised. We propose five versions of this problem using different objective functions, and algorithms to solve them. This work has potential applications in geographic map schematisation and metro map layout.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_8
Classifications:M Methods > M.900 Tree
G Algorithms and Complexity > G.210 Bends
ID Code:762

Repository Staff Only: item control page


M. Blum, R. W. Floyd, V. R. Pratt, R. L. Rivest and R. E. Tarjan. Time bounds for selection. Journal of Comp. and Sys. Sciences, vol. 7, no. 4, p. 448-461, 1973.

U. Brandes, M. Eiglsperger, M. Kaufmann and D. Wagner. Sketch-driven orthogonal graph drawing. In Proc. Graph Drawing 2002, p. 1-11, 2002.

S. Cabello, M. de Berg and M. van Kreveld. Schematization of networks. Computational Geometry and Applications, vol. 30, p. 223-238, 2005.

S. Cabello and M. van Kreveld. Approximation algorithms for aligning points. Algorithmica, vol. 37, p. 211-232, 2003.

M. Eiglsperger, S. P. Fekete and G. W. Klau. Orthogonal graph drawing. Drawing Graphs, p. 121-171, Springer-Verlag Berlin Heidelberg, 2001.

H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proc. ACM-SIAM Symp. Discrete Alg., p. 434-443, 1990.

S. H. Hong, D. Merrick and H. A. D. do Nascimento. The metro map layout problem. In Proc. Graph Drawing 2004, p. 482-491, 2004.

U. Lauther and A. Stübinger. Generating schematic cable plans using springembedder methods. In Proc. Graph Drawing 2001, p. 465-466, 2002.

L. Lovasz and M. D. Plummer. Matching Theory. Elsevier, Amsterdam, 1986.

D. Merrick and J. Gudmundsson. Path simpli¯cation for metro map layout. Submitted to Graph Drawing, June 2006.

G. Neyer. Line simplification in restricted orientations. In Proc. of the 6th International workshop on Algorithms and Data Structures, p. 13-24, 1999.

M. Nöllenburg and A. Wolff. A mixed-integer program for drawing high-quality metro maps. In Proc. Graph Drawing 2005, p. 321-333, 2006.

J. M. Stott and P. Rodgers. Metro map layout using multicriteria optimization. In Proc. Information Visualisation, p. 355-362, 2004.