Metro Maps

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.

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.

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].

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.