Wu, Niederman, Takahashi and Nöllenburg – A SURVEY ON COMPUTING SCHEMATIC NETWORK MAPS 2022

Description

This survey reviews recent algorithmic work on schematic (metro) network maps, focusing on the trade-off between solution quality (globality) and interactivity (running time). The authors formalize the Metro Graph problem and introduce a taxonomy scoring combinatorial, geometric, and optimality criteria to position methods along global-versus-local and slow-versus-fast axes. They summarize network-layout approaches—force-based, multi-criteria hill-climbing, mixed-integer programming (MIP) for global optima, least-squares/energy methods, stroke-based schematization—and report typical runtimes and scalability. Labeling techniques are categorized by whether labeling is integrated with layout, the labeling optimality, and adjustment strategies; integrated MIP/hill-climbing yields higher quality but long runtimes, while decoupled or greedy/energy methods enable interactive performance at the cost of completeness or optimality. The survey highlights metro maps as visual metaphors and reviews online tools and applications. It concludes that algorithms balance constraints versus speed, notes the need for benchmarks and scalable methods that handle global constraints, and identifies interactive, high-quality automatic schematization as an open research direction.