User Hints for map labeling

Cartography is one of the oldest forms of visualization. It has applications not only in geography but in many other science fields. A significant visual problem in cartography is the map-labeling problem, which consists of assigning positions for the labels of graphical features of a map so that these elements can be uniquely identified. Although much research has been done on map labeling, practical labeling processes still demand intensive manual work to produce high-quality solutions. One reasons for this is that the optimization problems associated with map labeling are NP-hard. More importantly, existing automatic labeling methods do not incorporate all kinds of domain knowledge that may be of interest for a cartographer. In the present paper, we describe an interactive framework for assisting cartographers in the map-labeling problem. We treat labeling processes as an optimization task, and support human interaction combined with fully automatic methods in a general framework that we call User Hints. An interactive map-labeling system based on the User Hints framework is presented, and an evaluation of such system with real experts in cartography is described. This evaluation shows that our interactive map-labeling framework is promising.