Multi-stack Boundary Labeling Problems

The

boundary labeling

problem was recently introduced in [5] as a response to the problem of labeling dense point sets with large labels. In boundary labeling, we are given a rectangle

R

which encloses a set of

n

sites. Each site is associated with an axis-parallel rectangular label. The main task is to place the labels in distinct positions on the boundary of

R

, so that they do not overlap, and to connect each site with its corresponding label by non-intersecting polygonal lines, so called

leaders

. Such a label placement is referred to as

legal label placement

.

In this paper, we study boundary labeling problems along a new line of research. We seek to obtain labelings with labels arranged on more than one stacks placed at the same side of

R

. We refer to problems of this type as

multi-stack boundary labeling problems

.

We present algorithms for

maximizing the uniform label size

for boundary labeling with two and three stacks of labels. The key component of our algorithms is a technique that combines the merging of lists and the bounding of the search space of the solution. We also present NP-hardness results for multi-stack boundary labeling problems with labels of variable height.