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

• Published in 2010
• Added on 2011-04-07

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.

Links

• http://www.ncbi.nlm.nih.gov/pubmed/20498505

Other information

BibTeX entry

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