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.

Experimental Results

Geographic layout of the Sydney metro system.
Metro map of Sydney generated by our method.

The example of the metro map of Sydney, Australia shows the result of our 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 received the graduation award 2005/06 of the Faculty of Informatics for his Master's thesis “Automated Drawing of Metro Maps” [4].

Press reports

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. It can be obtained from the FAZ archive.

Publications

  1. Alexander Wolff. Drawing subway maps: A survey. Informatik - Forschung & Entwicklung, 22(1):23-44, 2007. [ html | pdf ]
  2. Marc Benkert, Martin Nöllenburg, Takeaki Uno, and Alexander Wolff. Minimizing intra-edge crossings in wiring diagrams and public transport maps. In Michael Kaufmann and Dorothea Wagner, editors, Proc. 14th Internat. Sympos. Graph Drawing (GD'06), volume 4372 of Lecture Notes in Computer Science, pages 270-281. Springer-Verlag, 2007. [ bib | pdf ]
  3. Martin Nöllenburg and Alexander Wolff. A mixed-integer program for drawing high-quality metro maps. In Patrick Healy and Nikola S. Nikolov, editors, Proc. 13th Internat. Sympos. Graph Drawing (GD'05), volume 3843 of Lecture Notes in Computer Science, pages 321-333. Springer-Verlag, 2006. [ bib | html | pdf ]
  4. Martin Nöllenburg. Automated drawing of metro maps. Master's thesis, Fakultät für Informatik, Universität Karlsruhe, August 2005. [ bib | pdf ]
  5. Martin Nöllenburg. Automated drawing of metro maps. Technical Report 2005-25, Fakultät für Informatik, Universität Karlsruhe, 2005. [ bib | html | pdf ]