The Metro Map Layout Problem

Hong, Seok-Hee and Merrick, Damian and Do Nascimento, Hugo A. D. (2004) The Metro Map Layout Problem. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 482-491 (Official URL:

Full text not available from this repository.


We initiate a new problem of automatic metro map layout. In general, a metro map consists of a set of lines which have intersections or overlaps. We define a set of aesthetic criteria for good metro map layouts and present a method to produce such layouts automatically. Our method uses a variation of the spring algorithm with a suitable preprocessing step. The experimental results with real world data sets show that our method produces good metro map layouts quickly. A preliminary version of this paper was published in [5]. For a version of this paper with full-size colour images, see [6].

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_50
Classifications:J Applications > J.999 Others
M Methods > M.400 Force-directed / Energy-based
ID Code:620

Repository Staff Only: item control page


F. Bertault, A Force-Directed Algorithm that Preserves Edge Crossing Properties, Graph Drawing 99, LNCS 1731, pp. 351-358, Springer Verlag, 1999.

A. Frick, A. Ludwig and H. Mehldau, A Fast Adaptive Layout Algorithm for Undirected Graphs, Graph Drawing 94, LNCS 894, pp. 388-403, Springer Verlag, 1995.

C. Friedrich, jjgraph, personal communication.

K. Garland, Mr. Beck's Underground Map, Capital Transport Publishing, England, 1994.

S. -H. Hong, D. Merrick and H. A. D. do Nascimento, The Metro Map Layout Problem, Proc. of Australasian Symposium on Information Visualisation, ('04), Conference in Research and Practice in Information Technology, vol. 35, ACS, pp. 91-100, 2004.

S. -H. Hong, D. Merrick and H. A. D. do Nascimento, The Metro Map Layout Problem, Technical Report, 2004,

H. A. D. do Nascimento and P. Eades, User Hints for Map Labelling, Proc. of Australasian Computer Science Conference 2003, Conference on Research and Practice in Information Technology, vol 16, ACS, pp. 339-347, 2003.

K. Nesbitt, Multi-sensory Display of Abstract Data, PhD. Thesis, University of Sydney, 2003.

E. S. Sandvad, K. Grombak, L. Sloth and J. L. Knudsen, Metro Map Metaphor for Guided Tours on the Web: the Webvise guided Tour system , Proc. of International Conference on World Wide Web, pp. 326-333, 2001.

J. M. Stott and P. Rodgers, Metro Map Layout Using Multicriteria Optimization, Proc. of International Conference on Information Visualisation (IV04), pp. 355-362, 2004.

K. Sugiyama and K. Misue, Graph drawing by Magnetic Spring Model, Journal of Visual Languages and Computing, Vol.6, No.3, pp. 217-231, 1995.

E. R. Tufte, Visual Explanations, Graphics Press, Cheshire, 1997.

Cityrail Network,

O'Reilly book network,