Metro Maps
Summary
Metro maps are schematic maps for transportation networks such as metro or subway systems in large cities. However, in contrast to regular city maps, the goal is mainly to find a nice and clear layout of the network topology while geographic accuracy is less important. We formulate a mixed-integer program (MIP) that draws, given a geographic input graph, a metro map optimizing multiple quality criteria. We also show the NP-completeness of the problem.
Once the underlying network is drawn a secondary task is the metro line layout problem. Often significant parts of the transport infrastructure are used by multiple metro lines. In that case the order of these lines along the individual edges of the metro map needs to be determined as to minimize the number of line crossings. We give efficient algorithms for different versions of the metro line layout problem.
Experimental Results
The example of Sydney, Australia shows the result of our layout method given a geographic input network. The figure depicts the original layout of the train tracks on the left-hand side, and the schematic layout generated by our method on the right-hand side.
We distinguish hard and soft quality criteria for metro maps. Hard criteria represent the most important properties of real-world metro maps and need to be satisfied by any metro map layout. They comprise (a) minimum edge length, (b) preservation of the input topology, and (c) octilinearity of the drawing, i.e. all edges are constrained to be horizontal, vertical or 45-degree diagonal line segments.
Soft constraints are to be satisfied as good as possible. Here, the goals are (a) a minimum number of bends along the different metro lines, (b) preservation of the relative position between adjacent stations, and (c) a minimum total edge length. The above example of Sydney shows how these hard and soft constraints influence the outcome of our method.
Awards
- On May 3, 2006 Martin Nöllenburg received the NRW Undergraduate Science Award 2005 for the article “A mixed-integer program for drawing high-quality metro-maps” [3].
- On July 21, 2006 Martin Nöllenburg received the graduation award 2005/06 of the Faculty of Informatics for his Master's thesis “Automated Drawing of Metro Maps” [4].
Press reports
- Issue 4/2009 of the customer magazine bulletin of Swiss bank Credit Suisse reports about the joint work of Martin Nöllenburg and Alexander Wolff on drawing metro maps.
- On July 16, 2006 the German Sunday newspaper Frankfurter Allgemeine Sonntagszeitung no. 28/06 featured a two-page article “Die Schönheit des Untergrundes” (the beauty of the underground) by Klemens Polatschek.
Publications
Journal articles
Conference articles
- Marc Benkert, Martin Nöllenburg, Takeaki Uno, and Alexander Wolff.
Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transportation Maps.
In: Proceedings of the 14th International Symposium on Graph Drawing (GD'06) volume 4372 of Lecture Notes in Computer Science, pages 270-281. Springer, January 2007.
[ html ][ pdf ]
Master's Thesis
- Automated Drawing of Metro Maps.
Martin Nöllenburg.
Master's thesis, Universität Karlsruhe, August 2005.
[ pdf ]