Many-to-One Boundary Labeling with Backbones

Michael A. Bekos, Sabine Cornelsen, Martin Fink, Seok-Hee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter, Antonios SymvonisJ. Graph Algorithms Appl 2015 · DOI

TL;DR

This paper introduces "backbone labeling," a novel approach to annotating images with multiple labels per feature, using horizontal backbones and vertical leaders. They develop efficient algorithms for minimizing label count and leader length in crossing-free scenarios, and tackle the NP-hard problem of minimizing crossings when label order is flexible.

What Problem Does This Paper Address?

Labeling images with text to describe features is crucial in many applications, from technical drawings to medical atlases. Traditional map labeling methods struggle with large labels or dense feature sets. Boundary labeling, where labels are placed at the image boundary and connected to features via leaders, offers a solution. However, existing "many-to-one" boundary labeling models, where multiple features connect to a single label, face issues like tall labels, large routing areas, and leader crossings. This paper addresses these limitations by proposing "backbone labeling," a more compact and visually appealing model, and developing algorithms to optimize it.

Methods

The authors introduce the "backbone labeling" model, where each label has a horizontal backbone extending into the feature area, and vertical line segments connect features to this backbone. They then present dynamic programming algorithms for several optimization goals:

  • Minimizing Label Number (Crossing-Free): For infinite backbones, they achieve O(n) time complexity by leveraging the observation that vertically consecutive points of the same color can be grouped. For finite backbones, they use a dynamic program on gaps between points, resulting in O(n⁴|C|²) time.
  • Minimizing Total Leader Length (Crossing-Free): They adapt the dynamic programming approach for label number minimization. For infinite backbones, they achieve O(n²|C|ki) or O(n²K) time depending on label constraints. For finite backbones, the complexity increases to O(n⁷|C|²K²) or O(n⁷|C|²(Πkc)²) with label bounds.
  • Minimizing Crossings: For infinite backbones with fixed label order, they achieve O(n|C|) time. For finite backbones with fixed label order, the time complexity remains O(n|C|). When label order is flexible, they show the problem is NP-hard for finite backbones, while an efficient O(n + |C|³) algorithm exists for infinite backbones.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and theoretical analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Backbone Leaders as a Compact Model: The backbone leader approach significantly reduces the visual clutter compared to previous many-to-one labeling methods by eliminating the need for a dedicated track-routing area and using less "ink."
  • Dynamic Programming for Optimization: The core algorithmic strategy relies on dynamic programming, breaking down the problem into smaller subproblems based on point positions and colors.
  • Splitting Instances: A key insight for crossing-free labeling is how backbones can effectively split the problem instance into independent subinstances, simplifying the optimization process.
  • NP-Hardness of Flexible Crossing Minimization: The paper demonstrates that while minimizing crossings with a fixed label order is tractable, allowing flexible label order makes the problem NP-hard for finite backbones, highlighting a fundamental complexity barrier.
  • Gadgets for NP-Hardness Proof: The NP-hardness proof for flexible crossing minimization ingeniously uses "blocker" and "range restrictor" gadgets to construct a reduction from the Fixed Linear Crossing Number problem.

Key Results

  • Efficient algorithms for minimizing label number and total leader length in crossing-free backbone labelings.
  • An efficient algorithm for minimizing crossings with fixed label order for infinite backbones (O(n|C|)).
  • Demonstration that minimizing crossings with flexible label order is NP-hard for finite backbones.
  • An efficient algorithm for minimizing crossings with flexible label order for infinite backbones (O(n + |C|³)).

Limitations and Future Work

  • NP-Hardness for Finite Backbones with Flexible Order: The NP-hardness result for finite backbones with flexible label order suggests that finding optimal solutions in such scenarios will likely require approximation algorithms or heuristics.
  • Empirical Evaluation: The paper is primarily theoretical. An important future direction would be to empirically evaluate the performance of the proposed algorithms on real-world datasets and compare them with existing methods.
  • Practical Considerations: While the paper addresses theoretical aspects, future work could explore practical considerations like label text fitting within the defined boundaries and handling more complex feature shapes.
  • Generalizations: Extending the backbone labeling model to handle 3D data or dynamic environments could be interesting avenues for future research.

Summary updated

BibTeX
@article{bekos2015many,
  author = {Michael A. Bekos and Sabine Cornelsen and Martin Fink and Seok-Hee Hong and Michael Kaufmann and Martin Nöllenburg and Ignaz Rutter and Antonios Symvonis},
  title = {{Many-to-One Boundary Labeling with Backbones}},
  journal = {J. Graph Algorithms Appl.},
  year = {2015},
  doi = {10.7155/jgaa.00379},
}
Figure