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.

The work is co – funded by the European Social Fund (75%) and National Resources (25%) – Operational Program for Educational and Vocational Training II (EPEAEK II) and particularly the Program PYTHAGORAS.