[Back]

B. Niedermann, M. Nöllenburg:
"An Algorithmic Framework for Labeling Road Maps";
Talk: International Conference on Geographic Information Science, Montreal, Canada; 2016-09-27 - 2016-09-30; in: "Geographic Information Science 9th International Conference", (2016), ISBN: 978-3-319-45737-6; 308 - 322.

Given an unlabeled road map, we consider, from an algorithmic
perspective, the cartographic problem of placing non-overlapping
road labels embedded in the roads. We first decompose the road network
into logically coherent road sections, i.e., parts of roads between two junctions.
Based on this decomposition, we present and implement a new and
versatile framework for placing labels in road maps such that the number
of labeled road sections is maximized. In an experimental evaluation
with road maps of 11 major cities we show that our proposed labeling
algorithm is both fast in practice and that it reaches near-optimal
solution quality, where optimal solutions are obtained by mixed-integer
linear programming. In direct comparison, our algorithm consistently
outperforms the standard OpenStreetMap renderer Mapnik.

http://publik.tuwien.ac.at/files/publik_257088.pdf