Fink, Haverkort, Nöllenburg, Roberts M, Schuhmann and Wolff – DRAWING METRO MAPS USING BÉZIER CURVES 2013

Description

This paper introduces a novel method for automatically drawing metro maps using curvilinear Bézier curves rather than traditional octilinear polylines. Motivated by usability and visual smoothing, the authors define design criteria: smooth tangents at stations (B1), minimal number of curve segments per line (B2), and avoidance of inflection points (B3). Their contribution is a force-directed algorithm that directly represents and manipulates cubic Bézier curves via new forces on vertices, tangents, and control-point distances, plus standard vertex forces and geographic attraction. Intersections are checked via convex-hull and polygonization approximations, and a force-limiting scheme prevents crossings. A postprocessing merging step combines consecutive curves (using virtual degree-2 and degree-4 vertices) to reduce visual complexity. The implementation (Java) was tested on real networks (London, Vienna, Montréal, Sydney), showing substantial curve reduction; the largest instance (London) ran in 224s. Future work includes global C2 spline fitting, better merging at other vertex degrees, and integrating label placement.