TY - GEN

T1 - Many-to-one boundary labeling

AU - Kao, Hao Jen

AU - Lin, Chun-Cheng

AU - Yen, Hsu Chun

PY - 2007/8/2

Y1 - 2007/8/2

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. To our knowledge, all 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. Minimizing the total number of crossings in boundary labeling becomes a critical design issue as crossing is often regarded as the main source of confusion in visualization. In this paper, we consider the crossing minimization problem for multi-site-to-one-label boundary labeling, i.e., finding the placements of labels and leaders such that the total number of crossings among leaders is minimized. We show the crossing minimization problem to be NP-complete under certain one-side and two-side labeling schemes. Subsequently, approximation algorithms are derived for the above intractable problems. We also present an O(n2 log3 n)-time algorithm for the problem of minimizing the total leader length for multi-site-to-one- label boundary labeling, where n is the number of labels.

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. To our knowledge, all 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. Minimizing the total number of crossings in boundary labeling becomes a critical design issue as crossing is often regarded as the main source of confusion in visualization. In this paper, we consider the crossing minimization problem for multi-site-to-one-label boundary labeling, i.e., finding the placements of labels and leaders such that the total number of crossings among leaders is minimized. We show the crossing minimization problem to be NP-complete under certain one-side and two-side labeling schemes. Subsequently, approximation algorithms are derived for the above intractable problems. We also present an O(n2 log3 n)-time algorithm for the problem of minimizing the total leader length for multi-site-to-one- label boundary labeling, where n is the number of labels.

KW - Boundary labeling

KW - Map labeling

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

U2 - 10.1109/APVIS.2007.329277

DO - 10.1109/APVIS.2007.329277

M3 - Conference contribution

AN - SCOPUS:34547377381

SN - 1424408083

SN - 9781424408085

T3 - Asia-Pacific Symposium on Visualisation 2007, APVIS 2007, Proceedings

SP - 65

EP - 72

BT - Asia-Pacific Symposium on Visualisation 2007, APVIS 2007, Proceedings

T2 - 6th Asia-Pacific Symposium on Visualisation 2007, APVIS 2007

Y2 - 5 February 2007 through 7 February 2007

ER -