A Mixed-Integer Program for Drawing High-Quality Metro Maps

Nöllenburg, Martin and Wolff, Alexander (2006) A Mixed-Integer Program for Drawing High-Quality Metro Maps. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 321-333 (Official URL: http://dx.doi.org/10.1007/11618058_29).

Full text not available from this repository.

Abstract

In this paper we investigate the problem of drawing metro maps which is defined as follows. Given a planar graph G of maximum degree 8 with its embedding and vertex locations (e.g. the physical location of the tracks and stations of a metro system) and a set mathcal L of paths or cycles in G (e.g. metro lines) such that each edge of G belongs to at least one element of mathcal L, draw G and mathcal L emph{nicely}. We first specify the niceness of a drawing by listing a number of hard and soft constraints. Then we present a mixed-integer program (MIP) which always finds a drawing that fulfills all hard constraints (if such a drawing exists) and optimizes a weighted sum of costs corresponding to the soft constraints. We also describe some heuristics that speed up the MIP. We have implemented both the MIP and the heuristics. We compare their output to that of previous algorithms for drawing metro maps and to official metro maps drawn by graphic designers.

Item Type:Conference Paper
Additional Information:10.1007/11618058_29
Classifications:M Methods > M.999 Others
M Methods > M.600 Planar
P Styles > P.999 Others
P Styles > P.540 Planar
ID Code:701

Repository Staff Only: item control page

References

T. Barkowsky, L. J. Latecki, and K. F. Richter.: Schematizing maps: Simplification of geographic shape by discrete curve evolution. C. Freksa, W. Brauer, C. Habel, and K. F. Wender, editors, Proc. Spatial Cognition II, volume 1849 of Lecture Notes in Artificial Intelligence, pages 41--53, 2000.

C. Binucci, W. Didimo, G. Liotta, and M. Nonato.: Orthogonal drawings of graphs with vertex and edge labels. Comp. Geometry: Theory & Appl., 32(2):71--114, 2005.

U. Brandes, M. Eiglsperger, M. Kaufmann, and D. Wagner.: Sketch-driven orthogonal graph drawing. Proc. 10th Int. Symp. on Graph Drawing (GD'02), volume 2528 of Lecture Notes in Computer Science, pages 1--11. Springer-Verlag, 2002.

S. Cabello, M. d. Berg, S. v. Dijk, M. v. Kreveld, and T. Strijk.: Schematization of road networks. Proc. 17th Annual Symp. on Computational Geometry (SoCG'01), pages 33--39, New York, 2001. ACM Press.

G. di Battista, P. Eades, R. Tamassia, and I. G. Tollis.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.

S. H. Hong, D. Merrick, and H. A. D. d. Nascimento.: The metro map layout problem. In J. Pach, editor, Proc. 12th Int. Symp. on Graph Drawing (GD'04), volume 3383 of Lecture Notes in Computer Science, pages 482--491. Springer-Verlag, 2005.

M. Nöllenburg.: Automated drawings of metro maps. Technical Report 2005-25, Universität Karlsruhe, 2005. Available at http://www.ubka.uni-karlsruhe.de/cgi-bin/psview?document=/ira/2005/25

M. Ovenden.: Metro Maps of the World. Capital Transport Publishing, 2003.

E. S. Sandvad, K. Gronbaek, L. Sloth, and J. L. Knudsen.: A metro map metaphor for guided tours on the Web: the Webvise Guided Tour System. Proc. 10th Int. World Wide Web Conf. (WWW'01), p. 326--333, Hong Kong, 2001. ACM Press.

J. M. Stott and P. Rodgers.: Metro map layout using ulticriteria optimization.Proc. 8th Int. Conf. on Information Visualisation (IV'04), London, pages 355--362. IEEE, 2004.

Sydney CityRail.: www.cityrail.nsw.gov.au/networkmaps/network_map.pdf.

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