Nöllenburg – A SURVEY ON AUTOMATED METRO MAP LAYOUT METHODS 2014

Description

This survey reviews automated metro map layout research, framing the task into three interdependent problems: schematic network layout, station labeling, and metro-line crossing minimization. It distills ten common design principles—most importantly topology preservation, restricted edge orientations (usually octilinear), straight/monotone lines, clear interchange routing, good angular resolution, limited geometric distortion, uniform edge lengths, separation of unrelated features, balanced density, and legible labels—which guide algorithm design. The paper categorizes methods into path-based schematization, discrete curve evolution, force-based approaches, local and global optimization, stroke-based schematization, mixed-integer linear programming (MIP), and least-squares optimization, and discusses standalone labeling and line-ordering algorithms. Key complexity results include NP-hardness for octilinear bend minimization and several crossing-minimization variants; nonetheless, exact, heuristic, approximation, and fixed-parameter solutions exist for special cases. MIP yields high-quality labeled maps but can be slow; force and local methods are faster but sometimes produce lower-quality or locally suboptimal maps. The survey concludes that automated methods are valuable for templates and on-demand maps, but challenges remain in scaling, capturing global aesthetics, handling thick line bundles, and enabling interactive user constraints.