Batik, Terziadis, Wang, Nöllenburg and Wu – SHAPE-GUIDED MIXED METRO MAP LAYOUT 2022

Description

The paper presents a pipeline for creating mixed metro maps that embed user-defined guide shapes (polylines) into schematic transit diagrams. Motivated by designer examples, the authors formalize the mixed metro map problem and seven design principles—including octolinear constraints, topographic accuracy, uniform station spacing, scale-and-translation-only shape embedding, and hybrid edge orientation—and convert them into optimization criteria. Their three-stage algorithm first matches a network path to the guide shape with an adapted shape-preserving Dijkstra minimizing a direction-based integral Fréchet distance, inserting high-cost dummy edges when needed. Next, layout deformation occurs in two phases: a least-squares “smooth” fit optimizing shape approximation, uniform edge lengths, angular resolution, and geographic preservation; then a mixed layout that classifies edges as shape-tracing or octolinear, assigns octolinear slopes (resolving conflicts with the Hungarian algorithm), and minimizes rotation while keeping planarity. A final grid-alignment stage adapts the Octi framework to favor routing along the guide and produce exact octolinear/shape-aligned edges. Experiments on real networks show visually plausible results and scaling behavior; a 63-participant user study found high recognizability for simple shapes. Limitations include local optimization artifacts, unroutable edges, labeling and scalability issues; future work targets complex shapes, non-octolinear grids, and improved metrics.