Geodesic
Many-to-One Boundary Labeling
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 6th Asia-Pacific Symposium on Visualisation, APVIS 2007 , Tome 12 (2008) no. 3, pp. 319-356.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 or heuristics are derived for the above intractable problems. 
@article{JGAA_2008_12_3_a3,
     author = {Chun-Cheng Lin and Hao-Jen Kao and Hsu-Chun Yen},
     title = {Many-to-One {Boundary} {Labeling}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {319--356},
     publisher = {mathdoc},
     volume = {12},
     number = {3},
     year = {2008},
     doi = {10.7155/jgaa.00169},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00169/}
}
TY  - JOUR
AU  - Chun-Cheng Lin
AU  - Hao-Jen Kao
AU  - Hsu-Chun Yen
TI  - Many-to-One Boundary Labeling
JO  - Journal of Graph Algorithms and Applications
PY  - 2008
SP  - 319
EP  - 356
VL  - 12
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00169/
DO  - 10.7155/jgaa.00169
LA  - en
ID  - JGAA_2008_12_3_a3
ER  - 
%0 Journal Article
%A Chun-Cheng Lin
%A Hao-Jen Kao
%A Hsu-Chun Yen
%T Many-to-One Boundary Labeling
%J Journal of Graph Algorithms and Applications
%D 2008
%P 319-356
%V 12
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00169/
%R 10.7155/jgaa.00169
%G en
%F JGAA_2008_12_3_a3
Chun-Cheng Lin; Hao-Jen Kao; Hsu-Chun Yen. Many-to-One Boundary Labeling. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the 6th Asia-Pacific Symposium on Visualisation, APVIS 2007
					, Tome 12 (2008) no. 3, pp. 319-356. doi : 10.7155/jgaa.00169. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00169/

Cité par Sources :