[Zurück]

A. Gemsa, B. Niedermann, M. Nöllenburg:
"Placing Labels in Road Maps: Algorithms and Complexity";
Algorithmica (online), 82 (2020), S. 1881 - 1908.

A road map can be interpreted as a graph embedded in the plane, in which each vertex corresponds to a road junction and each edge to a particular road section. In this paper, we consider the computational cartographic problem to place non-over-lapping road labels along the edges so that as many road sections as possible are identified by their name, i.e., covered by a label. We show that this is NP-hard in general, but the problem can be solved in O(n3) time if the road map is an embed-ded tree with n vertices and constant maximum degree. This special case is not only of theoretical interest, but our algorithm in fact provides a very useful subroutine in exact or heuristic algorithms for labeling general road maps.

http://dx.doi.org/10.1007/s00453-020-00678-7

https://publik.tuwien.ac.at/files/publik_290118.pdf