Many-to-One Boundary Labeling with Backbones

Abstract

We study a boundary labeling problem, where multiple points may connect to the same label. In this new many-to-one model, a horizontal backbone reaches out of each label into the feature-enclosing rectangle. Feature points that need to be connected to this label are linked via vertical line segments to the backbone. We present dynamic programming algorithms for minimizing the total number of label occurrences and for minimizing the total leader length of crossing-free backbone labelings. When crossings are allowed, we aim at obtaining solutions with the minimum number of crossings. This can be achieved efficiently in the case of fixed label order; however, in the case of flexible label order we show that minimizing the number of leader crossings is NP-hard.