Boundary Labeling with Octilinear Leaders

An illustration with textual labels may be hard to read if the labels overlap parts of the illustration. Boundary labeling addresses this problem by attaching the labels to the boundary of a rectangle that contains all features. Then, each feature should be connected to its associated label through a polygonal line, called leader, such that no two leaders intersect. In this paper we study the boundary labeling problem with octilinear leaders, i.e., leaders involving horizontal, vertical, and diagonal segments. In order to produce crossing-free boundary labelings, we combine different pairs of octilinear leaders. Thus, we are able to overcome infeasibility problems that might arise if only a single type of leader is allowed. Our main contribution is a new algorithm for solving the total leader length minimization problem (i.e., the problem of finding a crossing-free boundary labeling, such that the total leader length is minimized) assuming labels of uniform size. We also present an NP-completeness result for the case where the labels are of arbitrary size. © 2009 Springer Science+Business Media, LLC