Drawing Subway Maps: A Survey
Informatik -- Forschung & Entwicklung, 22 (1):
23--44 (2007)DOI: 10.1007/s00450-007-0036-y
Abstract
This paper deals with automating the drawing of
subway maps. There are two features of schematic
subway maps that make them different from drawings
of other networks such as flow charts or
organigrams. First, most schematic subway maps use
not only horizontal and vertical lines, but also
diagonals. This gives more flexibility in the
layout process, but it also makes the problem
provably hard. Second, a subway map represents a
network whose components have geographic locations
that are roughly known to the users of such a map.
This knowledge must be respected during the search
for a clear layout of the network. For the sake of
visual clarity the underlying geography may be
distorted, but it must not be given up, otherwise
map users will be hopelessly confused. In this
paper we first give a rather generally accepted list
of rules that should be adhered to by a good subway
map. Next we survey three recent methods for
drawing subway maps, analyze their performance with
respect to the above rules, and compare the
resulting maps among each other and to official
subway maps drawn by graphic designers. We then
focus on one of the methods, which is based on
mixed-integer linear programming, a widely-used
global optimization technique. This method
guarantees to find a drawing that fulfills a subset
of the above-mentioned rules (if such a drawing
exists) and optimizes a weighted sum of costs that
correspond to the remaining rules. The method can
draw even large subway networks such as the London
Underground in an aesthetically pleasing manner,
similar to maps made by professional graphic
designers. If station labels are included in the
optimization process, so far only medium-size
networks can be drawn. Finally we give evidence why
drawing good subway maps is difficult (even without
labels).
