Nickel and Nöllenburg – DRAWING k-LINEAR METRO MAPS 2019

Description

The authors extend an octilinear mixed-integer linear programming (ILP) model to produce k-linear metro maps, where edges are restricted to k equidistant orientations (2k directions). Their global-optimization ILP enforces hard constraints for a k-linear coordinate system, per-edge direction assignment and minimum lengths, preservation of the input combinatorial embedding, and planarity via separation lines. Soft constraints optimize line straightness, topographicity (preserving input directions), and compactness (total edge length); these are combined in a weighted objective. The model uses redundant rotated coordinates and binary variables to encode directions and cyclic neighbor order; its size grows linearly with k. Experiments on Vienna and Washington DC for k=3,4,5 (implemented with IBM CPLEX) show higher k yields better topographicity but longer solve times (k=3 ≲20s, k=4 minutes, k=5 up to hours; near-optimal solutions within 2 minutes). Future work includes labeling, performance improvements, and interactive design tools.