The Hardness of Placing Street Names in a Manhattan Type Map

摘要

Map labeling is a classical key problem. The interest in this problem has grown over the last years, because of the need to churn out different types of maps from a growing and altering set of data. We will show that the problem of placing street names without conflicts in a rectangular grid of streets is NP-complete and APX-hard. This is the first result of this type in this area. Further importance of this result arises from the fact that the considered problem is a simple one. Each row and column of the rectangular grid of streets contains just one street and the corresponding name may be placed anywhere in that line.