Many-to-One Boundary Labeling with Backbones

Authors

  • Michael Bekos
  • Sabine Cornelsen
  • Martin Fink
  • Seok-Hee Hong
  • Michael Kaufmann
  • Martin Nöllenburg
  • Ignaz Rutter
  • Antonios Symvonis

DOI:

https://doi.org/10.7155/jgaa.00379

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.

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

Issue

Section

Articles

Categories