Many-to-One Boundary Labeling with Backbones
DOI:
https://doi.org/10.7155/jgaa.00379Abstract
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.Downloads
Download data is not yet available.
Downloads
Published
2015-12-01
How to Cite
Bekos, M., Cornelsen, S., Fink, M., Hong, S.-H., Kaufmann, M., Nöllenburg, M., … Symvonis, A. (2015). Many-to-One Boundary Labeling
with Backbones. Journal of Graph Algorithms and Applications, 19(3), 779–816. https://doi.org/10.7155/jgaa.00379
License
Copyright (c) 2015 Michael Bekos, Sabine Cornelsen, Martin Fink, Seok-Hee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter, Antonios Symvonis
This work is licensed under a Creative Commons Attribution 4.0 International License.