# Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming.

• Published in 2010
In the collection
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.

## Other information

doi
10.1109/TVCG.2010.81
issn
1077-2626
journal
IEEE transactions on visualization and computer graphics
pages
1--25
pmid
20498505

### BibTeX entry

@article{Nollenburg2010,
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.},
author = {N{\"{o}}llenburg, Martin and Wolff, Alexander},
doi = {10.1109/TVCG.2010.81},
issn = {1077-2626},
journal = {IEEE transactions on visualization and computer graphics},
month = {may},
pages = {1--25},
pmid = 20498505,
title = {Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming.},
url = {http://www.ncbi.nlm.nih.gov/pubmed/20498505},
year = 2010,
urldate = {2011-04-07},
collections = {Basically computer science}
}