TY - GEN

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

AU - Lin, Chun-Cheng

PY - 2010/5/6

Y1 - 2010/5/6

N2 - 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.

AB - 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.

KW - Automatic label placement

KW - Boundary labeling

KW - Information visualization

KW - Map labeling

UR - http://www.scopus.com/inward/record.url?scp=77951680820&partnerID=8YFLogxK

U2 - 10.1109/PACIFICVIS.2010.5429592

DO - 10.1109/PACIFICVIS.2010.5429592

M3 - Conference contribution

AN - SCOPUS:77951680820

SN - 9781424466849

T3 - IEEE Pacific Visualization Symposium 2010, PacificVis 2010 - Proceedings

SP - 185

EP - 192

BT - IEEE Pacific Visualization Symposium 2010, PacificVis 2010 - Proceedings

T2 - IEEE Pacific Visualization Symposium 2010, PacificVis 2010

Y2 - 2 March 2010 through 5 March 2010

ER -