Label placement in road maps

DOI10.1007/978-3-319-18173-8_16MaRDI QIDQ2947022zbMATH OpenOpenAlexFDO

Authors Andreas Gemsa, Benjamin Niedermann, Martin Nöllenburg

Publication date 21 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.07188

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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. We consider the 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 polynomial time if the road map is an embedded tree.

Recommendations

• Placing labels in road maps: algorithms and complexity
• scientific article; zbMATH DE number 1629849
• The hardness of placing street names in a Manhattan type map
• Three rules suffice for good label placement
• A UNIFIED APPROACH TO AUTOMATIC LABEL PLACEMENT

Cites work

• scientific article; zbMATH DE number 1629850 (Why is no real title available?)
• Label placement in road maps
• LABELING POINTS WITH CIRCLES
• Planar Formulae and Their Uses
• The hardness of placing street names in a Manhattan type map

Cited in

(7)

• The hardness of placing street names in a Manhattan type map
• Placing labels in road maps: algorithms and complexity
• scientific article; zbMATH DE number 1629850 (Why is no real title available?)
• Models and methods for cartographic label placement
• Label placement in road maps
• Mixed Map Labeling
• On the complexity of the Edge Label Placement problem

This page was built for publication: Label placement in road maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947022)