Fink, Lechner and Wolff – CONCENTRIC METRO MAPS 2014

Description

The paper introduces concentric metro maps: schematic drawings centered at a chosen point c where edges are composed only of circular arcs around c or straight radial segments through c. The authors formulate the layout problem as a mixed-integer linear program (MIP), representing stations in polar coordinates and restricting edges to at most three segments (max one radial). Binary variables encode angular orderings to prevent crossings and count bends; additional constraints forbid segment overlaps and stations on nonincident edges. The objective is a weighted sum minimizing deviations from geographic positions (angle and radius), bend counts (per edge and per line), and encouraging radial segments to lie between endpoints. The model can be extended to limit distinct radii/angles, equalize edge lengths, and control spacing. A Java prototype using Gurobi produced example maps for Vienna and Montréal, with runtimes from seconds to 15 minutes; results are promising though some features (lines through the center, full bend minimization) and advanced criteria remain to be implemented. Future work focuses on richer objectives and scalability.