2015/01/28 by Andreas Gemsa, Gemsa, Andreas, Benjamin Niedermann +3
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1501.07188
extended version of a CIAC 2015 paper
arxiv created 2015/01/28 · openalex publication_date 2015/01/28 · arxiv updated 2015/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.