%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-02-18T09:53:56.000+0100}, author = {N{\"o}llenburg, Martin and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2e928b80335aa36e954d2d93af300d933/awolff}, doi = {10.1109/TVCG.2010.81}, interhash = {7b99b573079bd16d9437003a39312a6a}, intrahash = {e928b80335aa36e954d2d93af300d933}, 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-02-18T12:36:59.000+0100}, title = {Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming}, volume = 17, year = 2011 }