Abstract
Metro maps are schematic diagrams of public
transport networks that serve as visual aids for
route planning and navigation tasks. It is a
challenging problem in network visualization to
automatically draw appealing metro maps. There are
two aspects to this problem that depend on each
other: the layout problem of finding station and
link coordinates and the labeling problem of placing
non-overlapping station labels. In this paper
we present a new integral approach that solves the
combined layout and labeling problem (each of which,
independently, is known to be NP-hard) using
mixed-integer programming (MIP). We identify seven
design rules used in most real-world metro maps. We
split these rules into hard and soft constraints and
translate them into a MIP model. Our MIP formulation
finds a metro map that satisfies all hard
constraints (if such a drawing exists) and minimizes
a weighted sum of costs that correspond to the soft
constraints. We have implemented the MIP model and
present a case study and the results of an expert
assessment to evaluate the performance of our
approach in comparison to both manually designed
official maps and results of previous layout
methods.
Users
Please
log in to take part in the discussion (add own reviews or comments).