Algorithms for automatic placement of labels in drawings and maps
Konstantinos G. Kakoulis, Ioannis G. Tollis · 1998
In this thesis we present a comprehensive study of the label (name) placement problem which has applications in many areas including cartography, geographic information systems, and graph drawing. We prove that the problem of assigning labels to a set of line segments (edges) is NP-Hard. For the first time we present efficient heuristics that solve the problem of assigning labels to a set of line segments. These techniques are more suitable for placing labels to edges of hierarchical drawings of graphs. Experimental results show that the techniques are effective for labeling many different drawing styles. Next, we introduce a unified approach for solving the general labeling problem where a graphical feature can be a node, edge, or area. Our approach does not favor the labeling of one type of graphical feature over another. Furthermore, labels are allowed to have arbitrary size and orientation. Next, we consider the problem of assigning multiple labels to each graphical feature of a drawing. We present a characterization of this problem along with techniques that solve it. Finally, we present techniques that minimally change a graph drawing to open-up space such that each graphical feature has a label assigned to it. We conclude with a discussion on design issues for a label placement software system.