KIT | KIT-Bibliothek | Impressum | Datenschutz

Placing Labels in Road Maps: Algorithms and Complexity

Gemsa, Andreas; Niedermann, Benjamin; Nöllenburg, Martin

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-overlapping 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(n 3 ) time if the road map is an embedded 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.

Open Access Logo

Verlagsausgabe §
DOI: 10.5445/IR/1000105842
Veröffentlicht am 16.06.2020
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2020
Sprache Englisch
Identifikator ISSN: 0178-4617, 1432-0541
KITopen-ID: 1000105842
Erschienen in Algorithmica
Band 82
Seiten 1881–1908
Vorab online veröffentlicht am 01.02.2020
Schlagwörter Map labeling, Road maps, NP-hardness, Efficient tree-based algorithm
Nachgewiesen in Scopus
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page