Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00379
Many-to-One Boundary Labeling with Backbones
Vol. 19, no. 3, pp. 779-816, 2015. Regular paper.
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.
Submitted: August 2014.
Reviewed: May 2015.
Revised: October 2015.
Accepted: November 2015.
Final: December 2015.
Published: December 2015.
Communicated by Henk Meijer
article (PDF)
BibTeX