Geodesic
Efficient Labeling of Collinear Sites
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. 357-380.

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

In this paper we study the map labeling problem where the sites to be labeled are restricted to a line L. Previous models studied in the map labeling literature fail to produce label placements (i.e. place each label next to the site it describes) without label overlaps for certain instances of the problem with dense point sets. To address this problem, we propose a new approach according to which, given n sites each associated with an axis-parallel rectangular label, we aim to place the labels in distinct positions on the "boundary" of L so that they do not overlap and do not obscure the site set, and to connect each label with its associated site through a leader such that no two leaders intersect. We evaluate our labeling model under two minimization criteria: (i) total leader length and (ii) total number of leader bends. We show that both problems are NP-complete if the labels can be placed on both sides of L, while we present polynomial time algorithms for the case where the labels can be placed on only one side of L. 
@article{JGAA_2008_12_3_a4,
     author = {Michael Bekos and Michael Kaufmann and Antonios Symvonis},
     title = {Efficient {Labeling} of {Collinear} {Sites}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {357--380},
     publisher = {mathdoc},
     volume = {12},
     number = {3},
     year = {2008},
     doi = {10.7155/jgaa.00170},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00170/}
}
TY  - JOUR
AU  - Michael Bekos
AU  - Michael Kaufmann
AU  - Antonios Symvonis
TI  - Efficient Labeling of Collinear Sites
JO  - Journal of Graph Algorithms and Applications
PY  - 2008
SP  - 357
EP  - 380
VL  - 12
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00170/
DO  - 10.7155/jgaa.00170
LA  - en
ID  - JGAA_2008_12_3_a4
ER  - 
%0 Journal Article
%A Michael Bekos
%A Michael Kaufmann
%A Antonios Symvonis
%T Efficient Labeling of Collinear Sites
%J Journal of Graph Algorithms and Applications
%D 2008
%P 357-380
%V 12
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00170/
%R 10.7155/jgaa.00170
%G en
%F JGAA_2008_12_3_a4
Michael Bekos; Michael Kaufmann; Antonios Symvonis. Efficient Labeling of Collinear Sites. 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. 357-380. doi : 10.7155/jgaa.00170. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00170/

Cité par Sources :