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

作者：Noellenburg Martin; Wolff Alexander

来源：IEEE Transactions on Visualization and Computer Graphics, 2011, 17(5): 626-641.

DOI：10.1109/TVCG.2010.81

• Network visualization
• graph drawing
• graph labeling
• metro map
• octilinear layout
• mixed-integer programming

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 nonoverlapping 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 an 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.

• 出版日期2011-5