Haunert and Niedermann – AN ALGORITHMIC FRAMEWORK FOR LABELING NETWORK MAPS 2015

Description

The paper presents DynProg, a dynamic-programming approach for automatic, occlusion-free labeling of metro-map station labels modeled as simple polygons (fat curves) to support octilinear and curved styles. It proves the general labeling decision problem NP-complete (reduction from Planar Monotone 3-SAT) and defines a restricted SoftMetroLineLabeling problem under three assumptions—Separated Labels, Transitivity, and a linear Imhof-inspired weight w=w1+w2+w3 that penalizes steep/curvy labels, inconsistent consecutive labels, and close switchovers. Under these assumptions they give optimal DP algorithms: one-sided instances in O(n k^2) and two-sided lines in O(n^2 k^4) (n stops, k candidates each). For multi-line maps they propose a four-step pipeline: generate CurvedStyle/OctilinStyle candidates, scale the map to ensure feasibility (via 2-SAT), pre-select to remove inter-line conflicts, then label lines independently with DP. Experiments on Sydney and Vienna show few removals, sub-2s runtimes, and substantially better, less cluttered results than a greedy baseline, matching prior visual quality while improving speed and avoiding overlaps.