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.
%0 Journal Article
%1 nw-dlhqm-TVCG11
%A Nöllenburg, Martin
%A Wolff, Alexander
%D 2011
%J IEEE Transactions on Visualization and Computer Graphics
%K gd-info1 graph_drawing graph_labeling metro_map mixed-integer_programming mykeypub myown network_visualization octilinear_layout
%N 5
%P 626--641
%R 10.1109/TVCG.2010.81
%T Drawing and Labeling High-Quality Metro Maps by
Mixed-Integer Programming
%V 17
%X 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.
@article{nw-dlhqm-TVCG11,
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. \par 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.},
added-at = {2024-04-29T21:12:31.000+0200},
author = {Nöllenburg, Martin and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2c3eb24ebe8d176b0ad33f1a9c4182e23/awolff},
doi = {10.1109/TVCG.2010.81},
interhash = {e953043459d05f6ff473f9a576e8abda},
intrahash = {c3eb24ebe8d176b0ad33f1a9c4182e23},
jourmonth = {may},
journal = {IEEE Transactions on Visualization and Computer Graphics},
keywords = {gd-info1 graph_drawing graph_labeling metro_map mixed-integer_programming mykeypub myown network_visualization octilinear_layout},
number = 5,
pages = {626--641},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/nw-dlhqm-10.pdf},
succeeds = {nw-mipdh-06},
timestamp = {2024-04-29T21:12:31.000+0200},
title = {Drawing and Labeling High-Quality Metro Maps by
Mixed-Integer Programming},
volume = 17,
year = 2011
}