Crossing-free many-to-one boundary labeling with hyperleaders

Chun-Cheng Lin*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

26 Scopus citations


In boundary labeling, each point site is uniquely connected to a label placed on the boundary of an enclosing rectangle by a leader, which may be a rectilinear or straight line segment. Most of the results reported in the literature for boundary labeling deal with the so-called one-to-one boundary labeling, i.e., different sites are labelled differently. In certain applications of boundary labeling, however, more than one site may be required to be connected to a common label. In this case, the presence of crossings among leaders often becomes inevitable such that the labeling often has a high degree of confusion in visualization. In this paper, for multisite-to-one-label boundary labeling, crossings among leaders are avoided by substituting hyperleaders for leaders and by applying dummy labels (i.e., copies/duplicates of labels). Minimizing the number of dummy labels becomes a critical design issue as dummy labels are not required in the initial setting. Therefore, we consider the problem of minimizing the number of dummy labels for multisite-to-one-label boundary labeling, i.e., finding the placements of labels and hyperleaders such that the total number of dummy labels is minimized and there are no crossings among hyperleaders. Furthermore, after the number of dummy labels is determined, minimizing the total hyperleader length as well as the bends of hyperleaders is also concerned in postprocessing procedure. In this paper, we present polynomial time algorithms for the above one-side and two-side labeling schemes, and show their correctness from a theoretical point of view. In addition, we provide a simulated annealing algorithm for the four-side labeling schemes with objective to minimize the total number of dummy labels as well as the total leader length. Experimental results show that our four-side solutions look promising, as compared to the optimal solutions.

Original languageEnglish
Title of host publicationIEEE Pacific Visualization Symposium 2010, PacificVis 2010 - Proceedings
Number of pages8
StatePublished - 6 May 2010
EventIEEE Pacific Visualization Symposium 2010, PacificVis 2010 - Taipei, Taiwan
Duration: 2 Mar 20105 Mar 2010

Publication series

NameIEEE Pacific Visualization Symposium 2010, PacificVis 2010 - Proceedings


ConferenceIEEE Pacific Visualization Symposium 2010, PacificVis 2010


  • Automatic label placement
  • Boundary labeling
  • Information visualization
  • Map labeling


Dive into the research topics of 'Crossing-free many-to-one boundary labeling with hyperleaders'. Together they form a unique fingerprint.

Cite this