Institute of Theoretical Informatics, Algorithmics

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.

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

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

  • 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

  1. Martin Nöllenburg, and Alexander Wolff.
    Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming.
    IEEE Transactions on Visualization and Computer Graphics, 17(5):626-641, May 2011.
    [ html ][ pdf ]

Conference articles

  1. Martin Nöllenburg.
    An Improved Algorithm for the Metro-Line Crossing Minimization Problem.
    In: Proceedings of the 17th International Symposium on Graph Drawing (GD'09) volume 5849 of Lecture Notes in Computer Science, pages 381-392. Springer, 2010.
    [ html ][ pdf ]
  2. 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 ]
  3. Martin Nöllenburg, and Alexander Wolff.
    A Mixed-Integer Program for Drawing High-Quality Metro Maps.
    In: Proceedings of the 13th International Symposium on Graph Drawing (GD'05) volume 3843 of Lecture Notes in Computer Science, pages 321-333. Springer, January 2006.
    [ html ][ pdf ]

Master's Thesis

  1. Automated Drawing of Metro Maps.
    Martin Nöllenburg.
    Master's thesis, Universität Karlsruhe, August 2005.
    [ pdf ]

Technical reports

  1. Martin Nöllenburg.
    Automated Drawing of Metro Maps.
    Technical Report 2005-25, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2005.
    [ html ][ pdf ]