% =============================================================================
% Maplab : The Map-Labeling Project
% -----------------------------------------------------------------------------
% file : maplab.bib
% content : The Map-Labeling Bibliography
% url : http://i11www.iti.uni-karlsruhe.de/map-labeling/bibliography/
% author : Alexander Wolff
% uses : url.sty or hyperref.sty
% \url{} allows linebreaks in URLs without hyphenation
% ----------------------------------------------------------------------------
% publishers and series
@String{LNCS = {Lecture Notes Comput. Sci.}}
@String{SV = {Springer-Verlag}}
@String{TF = {Taylor \& Francis}}
% journals
@String{CACM = {Commun. ACM}}
@String{CGTA = {Comput. Geom. Theory Appl.}}
@String{DCG = {Discrete Comput. Geom.}}
@String{EJOR = {European J. Oper. Res.}}
@String{IJCGA = {Internat. J. Comput. Geom. Appl.}}
@String{IJGIS = {Internat. J. Geograph. Inform. Sci.}}
@String{IPL = {Inform. Process. Lett.}}
@String{JA = {J. Algorithms}}
@String{JGAA = {J. Graph Algorithms Appl.}}
@String{JACM = {J. ACM}}
@String{NJC = {Nordic J. Comput.}}
@String{SICOMP= {SIAM J. Comput.}}
@String{TCS = {Theoret. Comput. Sci.}}
@String{TOCS = {Theory Comput. Systems}}
% institutions
@String{FU = {Fachbereich Mathematik und Informatik,
Freie Universit{\"a}t Berlin}}
@String{UU = {Department of Computer Science, Utrecht University}}
@String{UG = {Institut f{\"ur} Mathematik und Informatik,
Universit{\"a}t Greifswald}}
@String{UKA= {Fakult{\"a}t f{\"u}r Informatik, Universit{\"a}t Karlsruhe}}
% urls
@String{MAPLABBASE = {http://i11www.ira.uka.de/map-labeling/}}
@String{MAPLABBIB = MAPLABBASE # {bibliography/}}
@String{MAPLABURL = MAPLABBASE # {papers/}}
@String{AWPUBURL = {http://i11www.ira.uka.de/\~{}awolff/pub/}}
% END OF PREAMBLE
@TechReport{a-acnph-95,
author = {Fauzia Abbasi},
title = {Automated Cartographic Name Placement for
High-Density Point Features},
institution = {Department of Electrical and Computer Enginering,
Rutgers University, Piscataway, NJ},
year = 1995
}
@PhdThesis{a-anmps-84,
author = {John Ahn},
title = {Automatic Map Name Placement System},
school = {Renselaer Polytechnic Institute},
year = 1984
}
@TechReport{a-anps-84,
author = {John Ahn},
title = {Automatic Name Placement System},
institution = {Image Processing Laboratory, Electrical, Computer,
and Systems Engineering Department, Rensselaer
Polytechnic Institute, Troy, N.Y. 12181},
year = 1984,
number = {IPL-TR-063}
}
@MastersThesis{a-arll3-05,
author = {Kamran Ali},
title = {Automated Realtime Label Layout for 3D
Illustrations},
school = {Otto-von-Guericke University of Magdeburg,
Department of Simulation and Graphics},
year = 2005
}
@Misc{a-ccsb-95,
author = {Alf-Christian Achilles},
title = {The Collection of Computer Science Bibliographies},
howpublished = {\url{http://liinwww.ira.uka.de/bibliography/}},
year = 1995,
url = {http://liinwww.ira.uka.de/bibliography/}
}
@MastersThesis{a-cdgip-88,
author = {Hiromi Aonuma},
title = {Character Displaying in Geographical Information
Processing},
school = {Department of Computer Science and Communication
Engineering, Kyushu University},
year = 1988,
note = {in Japanese},
language = {japanese}
}
@InBook{a-ctt-62,
author = {Georges Alinhac},
title = {Cartographie Th{\'e}orique et Technique},
chapter = {IV},
publisher = {Institut G{\'e}ographique National},
address = {Paris},
language = {french},
year = 1962
}
@InProceedings{af-aesam-84,
author = {John Ahn and Herbert Freeman},
title = {{AUTONAP}---An Expert System for Automatic Map
Name Placement},
booktitle = {Proc. Internat. Sympos. Spatial Data
Handling (SDH'84)},
year = 1984,
pages = {544--569}
}
@inproceedings{af-elpar-03,
author = {Ronald Azuma and Chris Furmanski},
title = {Evaluating Label Placement for Augmented Reality
View Management},
booktitle = {ISMAR},
title = {Proc. IEEE-ACM Internat. Sympos. Mixed and Augmented
Reality (ISMAR'03)},
location = {Tokyo, Japan},
year = 2003,
pages = {66--75},
url = {http://dx.doi.org/10.1109/ISMAR.2003.1240689}
}
@TechReport{af-nppm-83,
author = {John Ahn and Herbert Freeman},
title = {The Name Placement Problem for Maps},
institution = {Image Processing Laboratory, Electrical, Computer,
and Systems Engineering Department, Rensselaer
Polytechnic Institute, Troy, N.Y. 12181},
year = 1983,
number = {IPL-TR-043}
}
@InProceedings{af-panp-83,
author = {John Ahn and Herbert Freeman},
title = {A Program for Automatic Name Placement},
booktitle = {Proc. Auto-Carto 6},
year = 1983,
pages = {444--453},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-6/pdf/a-program-for-automatic-name-placement.pdf}
}
@Article{af-panp-84,
author = {John Ahn and Herbert Freeman},
title = {A program for automatic name placement},
journal = {Cartographica},
volume = 21,
number = {2--3},
year = 1984,
pages = {101--109},
update = {97.07 agarwal}
}
@InProceedings{ah-altpd-95,
author = {David H. Alexander and Carl S. Hantman},
title = {Automating Linear Text Placement Within Dense
Feature Networks},
booktitle = {Proc. Auto-Carto 12},
publisher = {ACSM/ASPRS, Bethesda},
year = 1995,
pages = {311--320},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-12/pdf/automating-linear-text-placement-within-dense-feature-networks.pdf}
}
@Article{ahs-lli3d-05,
author = {Kamran Ali and Knut Hartmann and Thomas Strothotte},
title = {Label Layout for Interactive {3D} Illustrations},
journal = {Journal of the WSCG},
volume = 13,
number = 1,
pages = {1--8},
location = {Plzen, Czech Republic},
confmonth = {31~} # jan # { -- 4~} # feb,
note = {(13th Internat.\ Conf.\ in Central Europe on Computer
Graphics, Visualization and Computer Vision
WSCG'05)},
year = 2005
}
@InProceedings{aik-vspca-89,
author = {Hiromi Aonuma and Hiroshi Imai and Yahiko
Kambayashi},
title = {A Visual System of Placing Characters Appropriately
in Multimedia Map Databases},
booktitle = {Proc. IFIP TC 2/WG 2.6 Working Conf. on Visual
Database Systems},
editor = {T. L. Kunii},
year = 1989,
publisher = {North-Holland},
pages = {525--546}
}
@InProceedings{ak-dmvgd-93,
author = {Masatoshi Arikawa and Yahiko Kambayashi},
title = {Dynamic Maps as Views of Geographic Databases},
booktitle = {Proc. First Internat. Workshop on Mobile
Multimedia Communications},
pages = {C.1.6-1--C.1.6-4},
year = 1993,
month = dec
}
@Article{ak-dnpfi-91,
author = {Masatoshi Arikawa and Yahiko Kambayashi},
title = {Dynamic Name Placement Functions for Interactive Map
Systems},
journal = {The Australian Computer Journal},
year = 1991,
volume = 23,
number = 4,
pages = {133--147},
update = {98.04 strijk}
}
@Article{akk-agimd-97,
author = {Masatoshi Arikawa and Yahiko Kambayashi and Hiroshi
Kai},
title = {Adaptive Geographic Information Media Using Display
Agents for Name Placement},
journal = {Journal of the Geographic Information Systems
Association},
year = 1997,
pages = { },
language = {japanese},
note = {in Japanese},
update = {98.04 strijk}
}
@InProceedings{akk-dmcvv-94,
author = {Masatoshi Arikawa and Hideyo Kawakita and Yahiko
Kambayashi},
title = {Dynamic Maps as Composite Views of Varied Geographic
Database Servers},
booktitle = {Proc. First Internat. Conf. on Applications
of Databases},
series = LNCS,
volume = 819,
publisher = SV,
year = 1994,
pages = {142--157},
update = {98.04 strijk}
}
@Article{akk-egimc-93,
author = {Masatoshi Arikawa and Hideyo Kawakita and Yahiko
Kambayashi},
title = {An Environment for Generating Interactive Maps with
Compromises between Users' Requirements and
Limitations of Display Screens},
journal = {Trans. Journal of the Geographic Information Systems
Association},
year = 1993,
month = mar,
volume = 2,
pages = { },
language = {japanese},
note = {in Japanese}
}
@InProceedings{akksw-seahq-99,
author = {Pankaj K. Agarwal and Lars Knipping and Marc van
Kreveld and Tycho Strijk and Alexander Wolff},
title = {A Simple and Efficient Algorithm for High-Quality
Line Labeling},
booktitle = {Proc. 15th European Workshop
Comput. Geom. (EWCG'99)},
site = {Antibes},
publisher = {INRIA Sophia-Antipolis},
year = 1999,
pages = {93--96},
update = {00.03 bibrelex, 99.07 bibrelex}
}
@InProceedings{aks-lpmis-97,
author = {Pankaj K. Agarwal and Marc van Kreveld and Subhash
Suri},
title = {Label Placement by Maximum Independent Set in
Rectangles},
booktitle = {Proc. 9th Canadian Conf. on Computational
Geometry (CCCG'97)},
year = 1997,
confmonth = {11--14~} # aug,
location = {Kingston, Canada},
pages = {233--238},
url = {http://www.cs.uu.nl/\~{}marc/research/cartography.html},
preceeds = {aks-lpmis-98},
abstract = {Motivated by the problem of labeling maps, we
investigate the problem of computing a large
non-intersecting subset in a set of $n$ rectangles
in the plane. Our results are as follows. In $O(n
\log n)$ time, we can find an $O(log n)$-factor
approximation of the maximum subset in a set of $n$
arbitrary axis-parallel rectangles in the plane. If
all rectangles have unit height, we can find a
2-approximation in $O(n \log n)$ time. Extending
this result, we obtain a $(1 + k)$-approximation in
time $O(n log n + n^{2k-1})$ time, for any integer
$k \ge 1$.}
}
@Article{aks-lpmis-98,
author = {Pankaj K. Agarwal and Marc van Kreveld and Subhash Suri},
title = {Label placement by maximum independent set in rectangles},
journal = CGTA,
volume = 11,
year = 1998,
pages = {209--218},
url = {http://www.cs.uu.nl/\~{}marc/research/cartography.html},
succeeds = {aks-lpmis-97},
preceeds = {ksw-plsl-99},
update = {99.01 kreveld}
}
@TechReport{aks-lpmis-98t,
author = {Pankaj K. Agarwal and Marc van Kreveld and Subhash
Suri},
title = {Label Placement by Maximum Independent Set in
Rectangles},
institution = UU,
number = {UU-CS-1998-04},
year = 1998,
pdf = {ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-1998/1998-04.pdf},
}
@Article{amy-alegd-02,
author = {N. Abe and S. Masuda and K. Yamaguchi},
title = {An algorithm for labeling edges in a graph drawing},
journal = {IEICE Trans. Fundamentals of Electronics,
Communications \& Comput. Sci.},
year = 2002,
volume = {J85-A},
number = 3,
pages = {306--314},
jourmonth = mar,
language = {japanese},
note = {In Japanese}
}
@InProceedings{at-ppflp-05,
author = {Adriana C. F. Alvim and {\'E}ric D. Taillard},
title = {{POPMUSIC} for the Point Feature Label Placement},
booktitle = {Proc. Fifth Metaheuristics Internat. Conf. (MIC'05)},
pages = { },
year = 2005,
confmonth = aug,
location = {Wien}
}
@TechReport{at-ppflp-05t,
author = {Adriana C. F. Alvim and {\'E}ric D. Taillard},
title = {{POPMUSIC} for the Point Feature Label Placement},
institution = {HEIG-VD and ITA/IEC},
year = 2005,
address = {S{\~a}o Jos{\'e} dos Campos, Brazil},
pdf = {http://mistic.heig-vd.ch/taillard/articles.dir/alvim_taillard_final.pdf}
}
@Article{at-ppflp-09,
author = {Adriana C. F. Alvim and {\'E}ric D. Taillard},
title = {{POPMUSIC} for the Point Feature Label Placement},
journal = EJOR,
year = 2009,
volume = 192,
number = 2,
pages = {396--413},
url = {http://dx.doi.org/10.1016/j.ejor.2007.10.002},
doi = {10.1016/j.ejor.2007.10.002},
pdf = {http://mistic.heig-vd.ch/taillard/articles.dir/alvim_taillard_final.pdf},
abstract = {Point-feature label placement is the problem of
placing text labels adjacent to point features on a
map so as to maximize legibility. The goal is to
choose positions for the labels that do not give
rise to label overlaps and that minimize obscuration
of features. A practical goal is to minimize the
number of overlaps while considering cartographic
preferences. This article proposes a new heuristic
for solving the point feature label placement
problem based on the application of the POPMUSIC
frame. Computational experiments show that the
proposed heuristic outperformed other recent
metaheuristics approaches in the
literature. Experiments with problem instances
involving up to 10 million points show that the
computational time of the proposed heuristic
increases almost linearly with the problem size. New
problem instances based on real data with more than
13,000 labels are proposed.},
succeeds = {at-ppflp-05t}
}
@Article{b-aancp-94,
author = {Brenda S. Baker},
title = {Approximation Algorithms for {NP}-Complete Problems
on Planar Graphs},
journal = JACM,
volume = 41,
year = 1994,
pages = {153--180},
update = {97.03 kreveld}
}
@InProceedings{b-asnpc-97,
author = {Mathieu Barrault},
title = {An Automated System for Name Placement which
Complies with Cartographic Quality Criteria: {T}he
Hydrographic Network},
booktitle = {Proc. Conf. on Spatial Information
Theory (COSIT'97)},
location = {Pittsburgh, PA},
series = LNCS,
volume = 1329,
publisher = SV,
year = 1997,
pages = {499--500}
}
@TechReport{b-camp-73,
author = {A. Raymond Boyle},
title = {Computer Aided Map Compilation},
institution = {Department of Electrical Engineering, University of
Saskatchewan, Canada},
year = 1973
}
@InProceedings{b-naanp-82,
author = {Umit Basoglu},
title = {A New Approach to Automated Name Placement},
booktitle = {Proc. Auto-Carto 5},
year = 1982,
pages = {103--112},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-5/pdf/a-new-approach-to-automated-name-placement.pdf}
}
@PhdThesis{b-naanp-84,
author = {Umit Basoglu},
title = {A New Approach to Automated Name Placement Systems},
school = {University of Wisconsin-Madison},
year = 1984
}
@MastersThesis{b-patrr-93,
author = {Mathieu Barrault},
title = {Placement Automatique des Toponymes sur le
R{\'e}seau Routier au Million},
language = {french},
school = {DEA},
year = 1993
}
@PhdThesis{b-pcerp-98,
author = {Mathieu Barrault},
title = {Le placement cartographique des {\'e}critures:
r{\'e}solution d'un probl{\`e}me {\`a} forte
combinatoire et pr{\'e}sentant un grand nombre
de contraintes vari{\'e}es},
school = {Marne-la-Vall{\'e}e University},
year = 1998,
month = nov,
language = {french},
postscript = {ftp://ign/generalisation/COMMUNICATIONS/THESES/BARRAULT/MEMOIRE.ps.gz}
}
@InProceedings{b-ptm-83,
author = {M. Balodis},
title = {Positioning of Typography on Maps},
booktitle = {ACSM Fall Convention},
year = 1983,
pages = {28--44}
}
@TechReport{b-rsnmp-74,
author = {A. Raymond Boyle},
title = {Report on Symbol and Name Manipulation and
Placement},
institution = {Department of Electrical Engineering, University of
Saskatchewan, Canada},
year = 1974
}
@InProceedings{bbw-mlmoe-05,
author = {Lucas Bradstreet and Luigi Barone and Lyndon While},
title = {Map-labelling with a multi-objective evolutionary
algorithm},
booktitle = {Proceedings Genetic and Evolutionary Computation
Conf. (GECCO'05)},
year = 2005,
isbn = {1-59593-010-8},
pages = {1937--1944},
location = {Washington DC, USA},
doi = {http://doi.acm.org/10.1145/1068009.1068335},
publisher = {ACM Press},
location = {New York, NY, USA},
abstract = {We present a multi-objective evolutionary algorithm
approach to the map-labelling problem. Map-labelling
involves placing labels for sites onto a map such
that the result is easy to read and usable for
navigation. However, map-users vary in their
priorities and capabilities: for example,
sight-impaired users need to maximise font-size,
whereas other users may be willing to accept smaller
labels in exchange for increased clarity of bindings
of labels to sites. With a multi-objective approach,
we evolve a range of labellings from which users can
select according to their particular
circumstances. We present results from labelling two
maps, including a difficult, dense map of Newcastle
County in Delaware, which clearly illustrate the
advantages of the multi-objective approach.},
pdf = {http://www.wfg.csse.uwa.edu.au/publications/WFG2005c.pdf}
}
@InProceedings{bc-apsqm-94,
author = {D. Beus and D. Crockett},
title = {Automated Production of 1:24,000 Scale Quadrangle
Maps},
booktitle = {Proc. ASPRS/ACSM Annual Convention and
Exposition 1},
year = 1994,
pages = {94--99}
}
@InProceedings{bdln-lhod-02,
author = {Carla Binucci and Walter Didimo and Giuseppe Liotta
and Maddalena Nonato},
title = {Labeling Heuristics for Orthogonal Drawings},
booktitle = {Proc. Symp. 9th Internat. Symp. on Graph Drawing (GD'01)},
editor = {Petra Mutzel and Michael J{\"u}nger and Sebastian
Leipert},
year = 2002,
isbn = {3-540-43309-0},
pages = {139--153},
publisher = SV,
series = LNCS,
volume = 2265,
location = {Vienna},
}
@Article{bdln-odgvel-05,
author = {Carla Binucci and Walter Didimo and Giuseppe Liotta
and Maddalena Nonato},
title = {Orthogonal Drawings of Graphs with Vertex and Edge
Labels},
journal = CGTA,
year = 2005,
volume = 32,
number = 2,
pages = {71--114},
ee = {http://dx.doi.org/10.1016/j.comgeo.2005.02.001},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@Article{bdy-dml-06,
author = {Ken Been and Eli Daiches and Chee Yap},
title = {Dynamic Map Labeling},
journal = {IEEE Trans. Visualization \& Comput. Graphics},
year = 2006,
volume = 12,
number = 5,
pages = {773--780},
pdf = {http://doi.ieeecomputersociety.org/10.1109/TVCG.2006.136},
keywords = {Map labeling, dynamic maps, human-computer
interface, label placement, label selection, label
filtering, label consistency, computational
cartography, GIS, HCI, realtime, preprocessing},
abstract = {We address the problem of filtering, selecting and
placing labels on a dynamic map, which is
characterized by continuous zooming and panning
capabilities. This consists of two interrelated
issues. The first is to avoid label popping and
other artifacts that cause confusion and interrupt
navigation, and the second is to label at
interactive speed. In most formulations the static
map labeling problem is NP-hard, and a fast
approximation might have $O(n log n)$
complexity. Even this is too slow during
interaction, when the number of labels shown can be
several orders of magnitude less than the number in
the map. In this paper we introduce a set of
desiderata for "consistent" dynamic map labeling,
which has qualities desirable for navigation. We
develop a new framework for dynamic labeling that
achieves the desiderata and allows for fast
interactive display by moving all of the selection
and placement decisions into the preprocessing
phase. This framework is general enough to
accommodate a variety of selection and placement
algorithms. It does not appear possible to achieve
our desiderata using previous frameworks. \par Prior
to this paper, there were no formal models of
dynamic maps or of dynamic labels; our paper
introduces both. We formulate a general optimization
problem for dynamic map labeling and give a solution
to a simple version of the problem. The simple
version is based on label priorities and a versatile
and intuitive class of dynamic label placements we
call "invariant point placements". Despite these
restrictions, our approach gives a useful and
practical solution. Our implementation is
incorporated into the G-Vis system which is a
full-detail dynamic map of the continental USA. This
demo is available through any browser.}
}
@InCollection{be-aagp-97,
author = {Marshall Bern and David Eppstein},
title = {Approximation algorithms for geometric problems},
editor = {Dorit S. Hochbaum},
booktitle = {Approximation Algorithms for NP-Hard Problems},
publisher = {PWS Publishing Company},
address = {Boston, MA},
year = 1997,
pages = {296--345},
ISBN = {0-534-94968-1},
update = {97.07 smid, 97.03 agarwal+held, 95.09 mitchell}
}
@InProceedings{bfh-vmvar-01,
author = {Blaine Bell and Steven Feiner and Tobias
H{\"o}llerer},
title = {View Management for Virtual and Augmented Reality},
booktitle = {ACM Sympos. on User Interface Software and Technology
(UIST'01)},
pages = {101--110},
year = 2001,
location = {Orlando},
month = {11--14~} # nov,
keywords = {H.5.1 [Information Interfaces and Presentation]
Multimedia Information Interfaces Artificial,
augmented, and virtual realities; H.5.2 [Information
Interfaces and Presentation] User Interfaces
Graphical User Interfaces, Screen design; I.3.6
[Computer Graphics] Methodology and Techniques
Interaction Techniques; I.3.7 [Computer Graphics]
Three-Dimensional Graphics and Realism Virtual
Reality.},
pdf = {http://www.cs.columbia.edu/graphics/publications/uist01.pdf},
abstract = {We describe a view-management component for
interactive 3D user interfaces. By view management,
we mean maintaining visual constraints on the
projections of objects on the view plane, such as
locating related objects near each other, or
preventing objects from occluding each other. Our
view-management component accomplishes this by
modifying selected object properties, including
position, size, and transparency, which are tagged
to indicate their constraints. For example, some
objects may have geometric properties that are
determined entirely by a physical simulation and
which cannot be modified, while other objects may be
annotations whose position and size are flexible.
\par
We introduce algorithms that use upright rectangular
extents to represent on the view plane a dynamic and
efficient approximation of the occupied space
containing the projections of visible portions of 3D
objects, as well as the unoccupied space in which
objects can be placed to avoid occlusion. Layout
decisions from previous frames are taken into
account to reduce visual discontinuities. We present
augmented reality and virtual reality examples to
which we have applied our approach, including a
dynamically labeled and annotated environment.}
}
@Article{bgmr-eaatppr-01,
author = {Piotr Berman and Bhaskar DasGupta and
S. Muthukrishnan and Suneeta Ramaswami},
title = {Efficient Approximation Algorithm for Tiling and
Packing Problems with Rectangles},
journal = JA,
volume = 41,
number = 2,
year = 2001,
pages = {443--470},
}
@TechReport{bhhklrrstw-btp-02,
author = {Katharina Bach and Kristina Hanig and Tim Hoffmann
and Wolfgang Kresse and Julia L{\"o}cherbach and Paul
Rosenthal and Steffen Rudnick and Peter Schreiber
and Michael Thon and Alexander Wolff},
title = {{B}eschriftungsalgorithmen in {T}heorie \& {P}raxis},
institution = UG,
year = 2002,
number = {13/2002},
month = apr,
url = {http://www.math-inf.uni-greifswald.de/preprints/shadow/wolff02_13.rdf.html},
pdf = {http://www.math-inf.uni-greifswald.de/pub/full/prep/2002/wolff02_13.pdf},
language = {german, english},
annote = {with a chapter in English about open problems in
automated label placement},
note = {Available at \url{http://www.math-inf.uni-greifswald.de/preprints/shadow/wolff02_13.rdf.html}.}
}
@InProceedings{bkps-blotl-05,
author = {Michael A. Bekos and Michael Kaufmann and Katerina
Potika and Antonios Symvonis},
title = {Boundary labelling of optimal total leader length},
booktitle = {Proc. 10th Panhellenic Conf. on Informatics
(PCI'05)},
pages = {80--89},
year = 2005,
editor = {Panagiotis Bozanis and Elias Houstis},
volume = 3746,
series = LNCS,
publisher = SV,
ppt = {http://www.math.ntua.gr/\~{}mikebekos/pubs/PCI2005.ppt},
pdf = {http://www.math.ntua.gr/\~{}mikebekos/pubs/PCI2005.pdf}
}
@InProceedings{bkps-msblp-06,
author = {Michael A. Bekos and Michael Kaufmann and Ekaterini
Potika and Antonios Symvonis},
title = {On Multi-Stack Boundary Labeling Problems},
booktitle = {Proc. 10th WSEAS Internat. Conf. on
Computers (CSCC'06)},
pages = {2602--2608},
year = 2006,
editor = {Nikos Mastorakis},
pdf = {http://www.math.ntua.gr/\~{}mikebekos/pubs/WSEAS06.pdf}
}
@InProceedings{bkps-msblp-06a,
author = {Michael A. Bekos and Michael Kaufmann and Katerina
Potika and Antonios Symvonis},
title = {Mutli-Stack Boundary Labeling Problems},
booktitle = {Proc. 26th Conf. Foundations of Software Technology
and Theoretical Computer Science (FSTTCS'06)},
pages = {81--92},
year = 2006,
editor = {S. Arun-Kumar and N. Garg},
volume = 4337,
series = LNCS,
publisher = SV,
ppt = {http://www.math.ntua.gr/\~{}mikebekos/pubs/FSTTCS06.ppt},
pdf = {http://www.math.ntua.gr/\~{}mikebekos/pubs/FSTTCS06.pdf}
}
@InProceedings{bkps-plmll-06,
author = {Michael A. Bekos and Michael Kaufmann and Katerina
Potika and Antonios Symvonis},
title = {Polygon Labelling of Minimum Leader Length},
booktitle = {Proc. Asia-Pacific Symp. Information Visualization
(APVIS'06)},
pages = {15--21},
year = 2006,
editor = {Misue Kazuo and Sugiyama Kozo and Tanaka Jiro},
volume = 60,
series = {Conferences in Research and Practice in Information
Technology},
publisher = {Australian Computer Society, Inc.},
location = {Tokyo},
confmonth = feb,
pdf = {http://www.math.ntua.gr/\~{}mikebekos/pubs/APVIS06.pdf}
}
@InProceedings{bks-lcs-07,
author = {Michael A. Bekos and Michael Kaufmann and Antonios
Symvonis},
title = {Labeling collinear sites},
booktitle = {Proc. Asia-Pacific IEEE Symp. Information Visualization
(APVIS'07)},
pages = {45--51},
year = 2007,
confmonth = feb,
location = {Sydney}
}
@TechReport{bksw-blmea-04,
author = {Michael A. Bekos and Michael Kaufmann and Antonios
Symvonis and Alexander Wolff},
title = {Boundary Labeling: Models and Efficient Algorithms
for Rectangular Maps},
institution = UKA,
year = 2004,
number = {2004-15},
note = {Available at \url{http://digbib.ubka.uni-karlsruhe.de/volltexte/1000001841}.},
url = {http://digbib.ubka.uni-karlsruhe.de/volltexte/1000001841},
pdf = {http://digbib.ubka.uni-karlsruhe.de/volltexte/documents/1074}
}
@InProceedings{bksw-blmea-05,
author = {Michael A. Bekos and Michael Kaufmann and Antonios
Symvonis and Alexander Wolff},
title = {Boundary Labeling: Models and Efficient Algorithms
for Rectangular Maps},
booktitle = {Proc. 12th Internat. Sympos. on Graph Drawing (GD'04)},
pages = {49--59},
year = 2005,
editor = {J{\'a}nos Pach},
series = LNCS,
volume = 3383,
publisher = SV,
location = {New York},
confmonth = {29~} # sep # {~-- 2~} # oct,
url = {http://dx.doi.org/10.1007/b105810},
doi = {10.1007/b105810},
pdf = AWPUBURL # {bksw-blmea-05.pdf},
abstract = {In this paper, we present {\em boundary labeling},
a new approach for labeling point sets with large
labels. We first place disjoint labels around an
axis-parallel rectangle that contains the
points. Then we connect each label to its point such
that no two connections intersect. Such an approach
is common e.g.\ in technical drawings and medical
atlases, but so far the problem has not been studied
in the literature. The new problem is interesting in
that it is a mixture of a label-placement and a
graph-drawing problem.},
cites = {aes-vdsl3-95, bksw-blmea-04, c-cgitf-99,
fp-eldnl-99, fw-ppalm-91, fmc-alssm-96, gj-cigtn-79,
hs-asdch-92, i-mlp-99, il-elapm-03, km-allsd-03,
l-caicl-90, v-ghm-89, ws-mlb-96, z-prusa-97, ZZZ}
}
@Article{bksw-blmea-07,
author = {Michael A. Bekos and Michael Kaufmann and Antonios
Symvonis and Alexander Wolff},
title = {Boundary Labeling: Models and Efficient Algorithms
for Rectangular Maps},
journal = CGTA,
year = 2007,
volume = 36,
number = 3,
pages = {215--236},
doi = {10.1016/j.comgeo.2006.05.003},
url = {http://dx.doi.org/10.1016/j.comgeo.2006.05.003},
pdf = AWPUBURL # {bksw-blmea-07.pdf},
keywords = {Automated label placement, boundary labeling,
straight-line leaders, rectilinear leaders},
abstract = {In this paper, we present \emph{boundary labeling},
a new approach for labeling point sets with large
labels. We first place disjoint labels around an
axis-parallel rectangle that contains the point
sites. Then, we connect each label to its site such
that no two connections, so-called \emph{leaders},
intersect. Such an approach is common e.g.\ in
technical drawings and medical atlases, but so far
the problem has not been studied in the
literature. The new problem is interesting in that
it is a mixture of a label-placement and a
graph-drawing problem. \par We consider attaching
labels to one, two or all four sides of the
rectangle. We investigate rectilinear and
straight-line leaders. We present simple and
efficient algorithms that minimize the total length
of the leaders or, in the case of rectilinear
leaders, the total number of bends.},
succeeds = {bksw-blmea-04, bksw-blmea-05}
}
@InProceedings{bl-aslfn-95,
author = {Mathieu Barrault and Fran{\c c}ois Lecordix},
title = {An Automated System for Linear Feature Name
Placement which Complies with Cartographic Quality
Criteria},
booktitle = {Proc. Auto-Carto 12},
publisher = {ACSM/ASPRS, Bethesda},
location = {Charlotte, NC},
year = 1995,
confmonth = mar,
pages = {321--330},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-12/pdf/an-automated-system-for-linear-feature-name-placement.pdf}
}
@InProceedings{bnpw-oarcd-08,
author = {Ken Been and Martin N{\"o}llenburg and Sheung-Hung
Poon and Alexander Wolff},
title = {Optimizing Active Ranges for Consistent Dynamic Map
Labeling},
booktitle = {Proc. 24th Annu. ACM Sympos. Comput. Geom. (SoCG'08)},
pages = {10--19},
year = 2008,
location = {College Park, MD},
confmonth = jun,
pdf = AWPUBURL # {bnpw-oarcd-08.pdf},
url = {http://dx.doi.org/10.1145/1377676.1377681},
doi = {10.1145/1377676.1377681}
}
@Article{bnpw-oarcd-09,
author = {Ken Been and Martin N{\"o}llenburg and Sheung-Hung
Poon and Alexander Wolff},
title = {Optimizing Active Ranges for Consistent Dynamic Map
Labeling},
journal = CGTA,
year = 2009,
volume = { },
number = { },
pages = { },
note = {Appeared online at
\path|http://dx.doi.org/10.1016/j.comgeo.2009.03.006|.},
url = {http://dx.doi.org/10.1016/j.comgeo.2009.03.006},
doi = {10.1016/j.comgeo.2009.03.006},
pdf = AWPUBURL # {bnpw-oarcd-09.pdf},
succeeds = {bnpw-oarcd-08}
}
@InProceedings{bnpw-oarcdml-08,
author = {Ken Been and Martin N{\"o}llenburg and Sheung-Hung
Poon and Alexander Wolff},
title = {Optimizing Active Ranges for Consistent Dynamic Map
Labeling},
booktitle = {Proc. 24th European Workshop on Computational
Geometry (EuroCG'08)},
pages = {55--58},
year = 2008,
address = {Nancy},
confmonth = mar,
pdf = AWPUBURL # {bnpw-oarcdml-08.pdf}
}
@TechReport{bnr-nlawi-95t,
author = {Vineet Bafna and Babu Narayanan and R. Ravi},
title = {Nonoverlapping Local Alignments (Weighted
Independent Sets of Axis Parallel Rectangles)},
institution = {DIMACS},
number = {95-36},
month = {9~} # aug,
year = 1995,
postscript = {http://dimacs.rutgers.edu/techps/1995/95-36.ps}
}
@Article{bnr-nlawi-96,
author = {Vineet Bafna and Babu Narayanan and R. Ravi},
title = {Nonoverlapping local alignments (weighted
independent sets of axis-parallel rectangles)},
journal = {Discrete Applied Mathmatics},
volume = 71,
number = {1--3},
year = 1996,
issn = {0166-218X},
pages = {41--53},
doi = {http://dx.doi.org/10.1016/S0166-218X(96)00063-7},
publisher = {Elsevier},
address = {Amsterdam},
}
@InProceedings{bnr-nolaw-95,
author = {Vineet Bafna and Babu O. Narayanan and R. Ravi},
title = {Non-Overlapping Local Alignments (Weighted
Independent Sets of Axis Parallel Rectangles)},
booktitle = {Proc. 4th Internat. Workshop on
Algorithms and Data Structures ({WADS}'95)},
editor = {Selim G. Akl and Frank K. H. A. Dehne and
J{\"o}rg-R{\"u}diger Sack and Nicola Santoro},
location = {Kingston, Ontario, Canada},
month = {16--18~} # aug,
year = 1995,
series = LNCS,
volume = 955,
publisher = SV,
ISBN = {ISBN 3-540-60220-8},
pages = {506--517},
}
@InProceedings{bs-bbltd-06,
author = {Michael Bekos and Antonios Symvonis},
title = {BLer: A Boundary Labeller for Technical Drawings},
booktitle = {Proc. Symp. 13th Internat. Symp. on Graph Drawing (GD'05)},
pages = {503--504},
year = 2006,
editor = {Patrick Healy and Nikola S. Nikolov},
volume = 3843,
series = LNCS,
confmonth = {12--14~} # sep,
publisher = SV,
location = {Limerick, Ireland},
pdf = {http://www.math.ntua.gr/\~{}mikebekos/pubs/GD2005.pdf},
succeeds = {bksw-blmea-05},
note = {poster}
}
@PhdThesis{c-acnpr-88,
author = {A.C. Cook},
title = {Automated Cartographic Name Placement Using
Rule-Based Systems},
school = {Polytechnic of Wales},
year = 1988
}
@Article{c-anphc-00,
author = {Fran{\c c}ois Chiri{\'e}},
title = {Automated Name Placement with High Cartographic
Quality: City Street Maps},
journal = {Cartography and Geographic Information Science},
year = 2000,
volume = 27,
number = 2,
pages = {101--110},
update = {01.01 strijk}
}
@InCollection{c-cgitf-99,
author = {Bernard Chazelle and {36 co-authors}},
title = {The Computational Geometry Impact Task Force Report},
booktitle = {Advances in Discrete and Computational Geometry},
pages = {407--463},
publisher = {American Mathematical Society},
year = 1999,
editor = {B. Chazelle and J. E. Goodman and R. Pollack},
volume = 223,
address = {Providence, RI},
postscript = {http://compgeom.cs.uiuc.edu/\~{}jeffe/compgeom/files/taskforce.ps.gz}
}
@Article{c-csmap-87,
author = {L. Carstensen},
title = {A Comparison of Simple Mathematical Approaches to
the Placement of Spot Symbols},
journal = {Cartographica},
year = 1987,
volume = 24,
number = 3,
pages = {46-63}
}
@MastersThesis{c-iprpn-89,
author = {L. Christen},
title = {The Influence of Position Rankings on Point Name
Placement for Manually Produced Road Maps},
school = {Department of Geography, State University of New
York at Buffalo, New York},
year = 1989
}
@InProceedings{c-lprpa-85,
author = {Robert G. Cromley},
title = {An {LP} Relaxation Procedure for Annotating Point
Features Using Interactive Graphics},
booktitle = {Proc. Auto-Carto 7},
year = 1985,
pages = {127--132},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-7/pdf/an-lp-relaxation-procedure-for-annotating-point-features-using-interactive-graphics.pdf}
}
@MastersThesis{c-lpsl-03,
author = {Yu-Shin Chen},
title = {Labeling points on a single line},
school = {Department of Computer Science and Information
Engineering, National Taiwan University},
year = 2003,
month = jun
}
@PhdThesis{c-mdcus-95,
author = {Jon Christensen},
title = {Managing Design Complexity: Using Stochastic
Optimization in the Production of Computer Graphics},
school = {Harvard University},
year = 1995,
address = {Cambridge, MA},
month = jun
}
@Article{c-nmisr-04,
author = {Timothy M. Chan},
title = {A Note on Maximum Independent Sets in Rectangle
Intersection Graphs},
journal = IPL,
year = 2004,
volume = 89,
number = 1,
pages = {19--23},
url = {http://dx.doi.org/10.1016/j.ipl.2003.09.019},
doi = {10.1016/j.ipl.2003.09.019},
pdf = {http://www.math.uwaterloo.ca/\~{}tmchan/rect.pdf},
succeeds = {aks-lpmis-98}
}
@MastersThesis{c-ppanc-92,
author = {F. Chiri{\'e}},
title = {Programme de Positionnement Automatique des Noms de
Communes},
language = {french},
school = {COGIT, IGN, Paris},
year = 1992
}
@InProceedings{c-saapa-86,
author = {Robert G. Cromley},
title = {A Spatial Allocation Analysis of the Point
Annotation Problem},
booktitle = {Proc. 2nd Internat. Sympos. on Spatial Data
Handling (SDH'86)},
year = 1986,
pages = {38--49}
}
@InProceedings{cci-alcm-93,
author = {V. Consorti and L.P. Cordella and M. Iaccarino},
title = {Automated Lettering of Cadastral Maps},
booktitle = {Proc. Internat. Conf. on
Document Analysis and Recognition},
year = 1993,
pages = {129--132}
}
@InProceedings{cfms-etavs-97,
author = {Jon Christensen and Stacy Friedman and Joe Marks and
Stuart Shieber},
title = {Empirical Testing of Algorithms for Variable-Sized
Label Placement},
booktitle = {Proc. 13th Annu. ACM
Sympos. Comput. Geom. (SoCG'97)},
location = {Nice, France},
year = 1997,
pages = {415--417},
url = {http://doi.acm.org/10.1145/262839.263039},
doi = {10.1145/262839.263039}
}
@Article{cg-tsesl-08,
title = {Text Scaffolds for Effective Surface Labeling},
author = {Gregory Cipriano and Michael Gleicher},
journal = {IEEE Trans. Visualization \& Comput. Graphics},
year = 2008,
confmonth = {Nov.--Dec.},
volume = 14,
number = 6,
pages = {1675--1682},
abstract = {In this paper we introduce a technique for applying
textual labels to 3D surfaces. An effective labeling
must balance the conflicting goals of conveying the
shape of the surface while being legible from a
range of viewing directions. Shape can be conveyed
by placing the text as a texture directly on the
surface, providing shape cues, meaningful landmarks
and minimally obstructing the rest of the model. But
rendering such surface text is problematic both in
regions of high curvature, where text would be
warped, and in highly occluded regions, where it
would be hidden. Our approach achieves both labeling
goals by applying surface labels to a 'text
scaffold', a surface explicitly constructed to hold
the labels. Text scaffolds conform to the underlying
surface whenever possible, but can also float above
problem regions, allowing them to be smooth while
still conveying the overall shape. This paper
provides methods for constructing scaffolds from a
variety of input sources, including meshes,
constructive solid geometry, and scalar
fields. These sources are first mapped into a
distance transform, which is then filtered and used
to construct a new mesh on which labels are either
manually or automatically placed. In the latter
case, annotated regions of the input surface are
associated with proximal regions on the new mesh,
and labels placed using cartographic principles.},
pdf = {http://pages.cs.wisc.edu/\~{}gregc/Research/Papers/TextScaffolds.pdf}
}
@InProceedings{cj-picdn-90,
author = {Anthony C. Cook and Christopher B. Jones},
title = {A {P}rolog Interface to a Cartographic Database for
Name Placement},
booktitle = {Proc. 4th Internat. Sympos. on
Spatial Data Handling (SDH'90)},
year = 1990,
pages = {701--710}
}
@Article{cj-prbsc-90,
author = {Anthony C. Cook and Christopher B. Jones},
title = {A {P}rolog Rule-Based System for Cartographic Name
Placement},
journal = {Computer Graphics Forum},
year = 1990,
volume = 9,
number = 2,
pages = {109--126}
}
@Article{cll-lpsl-05,
author = "Yu-Shin Chen and D. T. Lee and Chung-Shou Liao",
title = "Labeling points on a single line",
journal = IJCGA,
volume = 15,
number = 3,
year = 2005,
pages = "261--277"
}
@InProceedings{cms-aclp-93,
author = {Jon Christensen and Joe Marks and Stuart Shieber},
title = {Algorithms for Cartographic Label Placement},
booktitle = {Proc. American Congress on Surveying
and Mapping 1},
year = 1993,
pages = {75--89}
}
@Article{cms-esapf-95,
author = {Jon Christensen and Joe Marks and Stuart Shieber},
title = {An Empirical Study of Algorithms for Point-Feature
Label Placement},
journal = {ACM Trans. Graphics},
year = 1995,
volume = 14,
number = 3,
pages = {203--232},
update = {98.01 strijk, wolff},
pdf = {http://www.eecs.harvard.edu/\~{}shieber/Biblio/Papers/tog-final.pdf}
}
@TechReport{cms-lpfmd-92,
author = {Jon Christensen and Joe Marks and Stuart Shieber},
title = {Labeling Point Features on Maps and Diagrams},
institution = {Harvard CS},
year = 1992,
number = {TR-25-92},
pdf = {http://www.eecs.harvard.edu/\~{}shieber/Biblio/Papers/label-algs-tog.pdf},
update = {98.01 strijk, wolff}
}
@InCollection{cms-ptlmd-94,
author = {Jon Christensen and Joe Marks and Stuart Shieber},
title = {Placing Text Labels on Maps and Diagrams},
editor = {Paul Heckbert},
booktitle = {Graphics Gems IV},
publisher = {Academic Press},
address = {Boston, MA},
year = 1994,
pages = {497--504},
keywords = {cartography, label placement, layout, relaxation,
simulated annealing},
update = {94.09 heckbert, 98.01 wolff},
annote = {Presents an algorithm to arrange text labels in a
way that avoids overlap. This is useful in
cartography.},
pdf = {http://www.eecs.harvard.edu/\~{}shieber/Biblio/Papers/jc.label.pdf}
}
@Article{crl-grasp-08,
author = {Gild{\'a}sio Lecchi Cravo and Glaydston Mattos
Ribeiro and Luiz Antonio Nogueira Lorena},
title = {A Greedy Randomized Adaptive Search Procedure for
the Point-Feature Cartographic Label Placement},
journal = {Comput. Geosci.},
year = 2007,
volume = 34,
number = 4,
pages = {373--386},
doi = {http://dx.doi.org/10.1016/j.cageo.2007.01.007},
pdf = {http://www.lac.inpe.br/\~{}lorena/glaydston/C\&Geo-GRASP.pdf},
jourpubl = {Pergamon Press, Tarrytown, NY, USA},
}
@InBook{d-c-96,
author = {Borden D. Dent},
title = {Cartography},
chapter = 14,
publisher = {Wm. C. Brown Publishers},
year = 1996
}
@InProceedings{d-cclsg-94,
author = {Yassine Djouadi},
title = {Cartage: A Cartographic Layout System Based on
Genetic Algorithms},
booktitle = {Proc. EGIS'94},
year = 1994,
pages = {48--56},
url = {http://libraries.maine.edu/Spatial/gisweb/spatdb/egis/eg94006.html}
}
@TechReport{d-dsrod-85,
author = {Jeffrey S. Doerschler},
title = {Data Structures Required for Overlap Detection in an
Expert Map Name Placement System},
institution = {Image Processing Laboratory, Electrical, Computer,
and Systems Engineering Department, Rensselaer
Polytechnic Institute, Troy, N.Y. 12181},
year = 1985,
number = {IPL-TR-077}
}
@MastersThesis{d-epanr-84,
author = {C. Destandeau},
title = {Essai de Positionnement Automatique de Num{\'e}ros
sur un R{\'e}seau Routier},
language = {french},
school = {IGN},
year = 1984
}
@PhdThesis{d-gaml-01,
author = {Steven van Dijk},
title = {Genetic Algorithms for Map Labeling},
school = {Department of Computer Science, Utrecht University},
year = 2001,
month = nov,
pdf = {http://www.cs.uu.nl/people/steven/download/thesis.pdf}
}
@PhdThesis{d-lpags-96,
author = {Yassine Djouadi},
title = {Logique Possibiliste et Am{\'e}lioration
G{\'e}n{\'e}tique pour la S{\'e}lection et
l'Agencement d'Objects Cartographiques},
school = {Laboratoire d'Ing{\'e}nierie des Syst{\`e}mes
d'Information, INSA},
language = {french},
year = 1996
}
@TechReport{d-mdpen-85,
author = {Jeffrey S. Doerschler},
title = {Map Data Production for an Expert Name Placement
System},
institution = {Image Processing Laboratory, Electrical, Computer,
and Systems Engineering Department, Rensselaer
Polytechnic Institute, Troy, N.Y. 12181},
year = 1985,
number = {IPL-TR-073}
}
@PhdThesis{d-rbsdm-87p,
author = {Jeffrey S. Doerschler},
title = {A Rule-Based System for Dense-Map Name Placement},
school = {Rensselaer Polytechnic Institute, Troy, N.Y. 12181},
year = 1987
}
@TechReport{d-rbsdm-87t,
author = {Jeffrey S. Doerschler},
title = {A Rule-Based System for Dense-Map Name Placement},
institution = {Center for Computer Aids for Industrial
Productivity, Rutgers University, Piscataway,
N.J. 08855-1390},
year = 1987,
number = {SR-006}
}
@TechReport{d-riaml-00,
author = {Alexandra Dorbes},
title = {Requirements for the Implementation of Automatic and
Manual Label Anti-Overlap Functions},
institution = {Eurocontrol Experimental Centre},
year = 2000,
number = 035,
month = dec,
url = {http://www.eurocontrol.int/eec/public/standard_page/DOC_Report_2000_035.html},
pdf = {http://www.eurocontrol.int/eec/gallery/content/public/document/eec/report/2000/035_Label_Anti-overlap_Functions.pdf}
}
@InProceedings{df-esdmn-89,
author = {Jeffrey S. Doerschler and Herbert Freeman},
title = {An Expert System for Dense-Map Name Placement},
booktitle = {Proc. Auto-Carto 9},
year = 1989,
pages = {215--224},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-9/pdf/an-expert-system-for-dense-map-name-placement.pdf}
}
@Article{df-rbsdm-92,
author = {Jeffrey S. Doerschler and Herbert Freeman},
title = {A Rule-Based System for Dense-Map Name Placement},
journal = CACM,
volume = 35,
year = 1992,
pages = {68--79},
update = {97.07 agarwal}
}
@InProceedings{dkmt-elglt-98,
author = {U{\u g}ur Do{\u g}rus{\"o}z and Konstantinos
G. Kakoulis and Brendan Madden and Ioannis
G. Tollis},
title = {Edge Labeling in the Graph Layout Toolkit},
booktitle = {Proc. Symp. 6th Internat. Symp. on Graph Drawing (GD'98)},
series = LNCS,
volume = 1547,
publisher = SV,
year = 1998,
month = aug,
pages = {356--363},
url = {http://link.springer.de/link/service/series/0558/tocs/t1547.htm}
}
@InProceedings{dksw-teqlp-99,
author = {Steven van Dijk and Marc van Kreveld and Tycho
Strijk and Alexander Wolff},
title = {Towards an Evaluation of Quality for Label Placement
Methods},
booktitle = {Proc. 19th Internat. Cartographic Conf. (ICC'99)},
year = 1999,
confmonth = {14--21~} # aug,
organization = {Internat. Cartographic Association},
address = {Ottawa, Canada},
vol = 1,
pages = {905--913},
pdf = AWPUBURL # {dksw-teqlp-99.pdf},
abstract = {The cartographic labeling problem is the problem of
placing text on a map. It is composed of two
phases. In the first, the question which map
features should in principle receive a label is
settled and the style (i.e.\ color and font) of
these labels is determined. The second phase
consists of the actual label placement. In this
phase for each feature one has to decide whether
there is in fact sufficient space and, if yes, the
best location and shape of the label must be
determined. This paper proposes a quality measure
for the result of the second phase, allowing the
comparison of label placement programs.}
}
@TechReport{dksw-teqnp-01,
author = {Steven van Dijk and Marc van Kreveld and Tycho
Strijk and Alexander Wolff},
title = {Towards an Evaluation of Quality for Names Placement
Methods},
institution = UU,
number = {UU-CS-2001-43},
year = 2001,
pdf = {ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-2001/2001-43.pdf}
}
@Article{dksw-teqnp-02,
author = {Steven van Dijk and Marc van Kreveld and Tycho
Strijk and Alexander Wolff},
title = {Towards an Evaluation of Quality for Names Placement
Methods},
journal = IJGIS,
publisher = TF,
year = 2002,
volume = 16,
number = 7,
pages = {641--661},
url = {http://www.swetswise.com/eAccess/viewToc.do?titleID=103831&yevoID=980131},
pdf = AWPUBURL # {dksw-teqnp-02.pdf},
cites = {af-aesam-84, a-ctt-62, b-asnpc-97, b-pcerp-98,
cj-picdn-90, d-c-96, df-rbsdm-92, ecms-gcla-97,
e-facnp-98, e-aclps-99, h-aanpa-82, hkr-ciuhd-93,
i-pnm-75, jk-eccg-98, j-cnpp-89, lp-insnp-86,
m-cbahc-95, m-lezac-99, pf-facat-96, p-smlpm-98,
rmmkg-ec-95, wkksa-seahq-99, ws-mlb-96, ZZZ},
succeeds = {dksw-teqlp-99},
abstract = {The cartographic labeling problem is the problem of
placing text on a map. This includes the positioning
of the labels, and determining the shape in the case
of line and area feature labels. There are many
rules and customs that describe aspects of good
label placement, like readability and clear
association. This paper gives a classification of
most label placement rules, and formalizes them into
a function that can serve as a quality measure for
label placement. If such a function is implemented,
it allows to compare the output of different label
placement programs. We give a simple and a more
refined example of the quality function.}
}
@InProceedings{dml-ieesn-89,
author = {C. Drinnan and C.G. Mattair and S.E. Luckey},
title = {An Interactive Expert Editing System for
Nomenclature Placement},
booktitle = {Technical Papers of the 1989 ASPRS/ACSM Annual
Convention},
year = 1989,
volume = 5,
pages = {221--230}
}
@InProceedings{dmm-pslsp-00,
author = {Srinivas Doddi and Madhav V. Marathe and Bernard
M.E. Moret},
title = {Point Set Labeling with Specified Positions},
booktitle = {Proc. 16th Annu. ACM Sympos. Comput. Geom. (SoCG'00)},
location = {Hongkong},
year = 2000,
month = {12--14~} # jun,
pages = {182--190},
postscript = {http://www.cs.unm.edu/\~{}moret/socg2000.ps}
}
@Article{dmm-pslsp-02,
author = {Srinivas Doddi and Madhav V. Marathe and Bernard
M.E. Moret},
title = {Point Set Labeling with Specified Positions},
journal = IJCGA,
year = 2002,
volume = 12,
number = {1--2},
pages = {29--66},
pdf = {http://www.worldscinet.com/ijcga/12/preserved-docs/1201n02/S0218195902000736.pdf},
url = {http://www.worldscinet.com/ijcga/12/1201n02/S0218195902000736.html},
succeeds = {dmm-pslsp-00},
abstract = {Motivated by applications in cartography and
computer graphics, we study a version of the
map-labeling problem that we call the
\emph{$k$-Position Map-Labeling Problem}: given a
set of points in the plane and, for each point, a
set of up to $k$ allowable positions, place uniform
and non-intersecting labels of maximum size at each
point in one of the allowable positions. This
version combines an aesthetic criterion and a
legibility criterion and comes close to actual
practice while generalizing the fixed-point and
slider models found in the literature. We present a
general heuristic that given an $e > 0$, runs in
time $O(n \log n + n \log(R^*/e) \log k)$, where
$R^*$ is the size of the optimal label, and
guarantees a constant approximation for any regular
labels. For circular labels, our technique yields a
($3.6 + e$)-approximation, improving in the case of
arbitrary placement over the previous bound of
approximately 19.5 obtained by Strijk and
Wolff \cite{sw-lpc-01}. We then extend our approach
to arbitrary positions, obtaining an algorithm that
is easy to implement and also substantially improves
the best approximation bounds. Our technique
combines several geometric and combinatorial
properties, which may be of independent interest.}
}
@InProceedings{dmmmz-mlg-97,
author = {Srinivas Doddi and Madhav V. Marathe and Andy
Mirzaian and Bernard M.E. Moret and Binhai Zhu},
title = {Map labeling and its generalizations},
booktitle = {Proc. 8th ACM-SIAM Sympos. on
Discrete Algorithms (SODA'97)},
location = {New Orleans, LA},
year = 1997,
month = {4--7~} # jan,
pages = {148--157},
postscript = {http://www.cs.unm.edu/\~{}moret/map.ps},
update = {98.01 strijk, wolff}
}
@InProceedings{dpp-poaam-03,
author = {Dirk D{\"o}rschlag and Ingo Petzold and Lutz
Pl{\"u}mer},
title = {Placing Objects Automatically in Areas of Maps},
booktitle = {Proc. 23rd Internat. Cartographic Conf. (ICC'03)},
pages = {269--275},
year = 2003,
address = {Durban, South Africa},
pdf = {http://www.geo.unizh.ch/\~{}petzold/publications/doerschlag_petzold_icc03.pdf},
abstract = {In this paper we present a vector-orientated
algorithm for placing objects (labels, diagrams,
etc.) automatically in areas of a map without
violating the boundary of the area. If the object
fits completely into the corresponding area, the
algorithm will identify all valid positions for the
midpoint of its bounding box and derive an optimal
position with regard to cartographic
requirements. The algorithm operates on objects that
can be approximated by rectangular bounding boxes
and maintain their orientation and size during the
placing process. Such a procedure is needed in the
automatic generation of choropleth maps or carto
diagrams. For instance in a map of Africa the trade
volume of each country can be indicated by a bar
chart placed inside the country s boundary. Further
examples are political maps, in which the names of
countries have to be placed within their
corresponding area.}
}
@Article{dqvz-pta3l-03,
author = {Rob Duncan and Jianbo Qian and Antoine Vigneron and
Binhai Zhu},
title = {Polynomial time algorithms for three-label point
labeling},
journal = TCS,
year = 2003,
volume = 296,
number = 1,
pages = {75--87},
doi = {10.1016/S0304-3975(02)00433-4},
url = {http://dx.doi.org/10.1016/S0304-3975(02)00433-4}
}
@InProceedings{dqz-pta3l-01,
author = {Rob Duncan and Jianbo Qian and Binhai Zhu},
title = {Polynomial time algorithms for three-label point
labeling},
booktitle = {Proc. 7th Annual Internat. Computing and
Combinatorics Conf. (COCOON'01)},
pages = {191--200},
year = 2001,
volume = 2108,
series = LNCS,
location = {Guilin},
month = {20--23~} # aug,
publisher = SV,
doi = {10.1007/3-540-44679-6},
url = {http://dx.doi.org/10.1007/3-540-44679-6},
abstract = {In this paper, we present an $O(n^3 \log n)$ time
solution for the following multi-label map labeling
problem: Given a set S of n distinct sites in the
plane, place at each site a triple of uniform
squares of maximum possible size such that all the
squares are axis-parallel and a site is on the
boundaries of its three labeling squares. We also
study the problem under the discrete model, i.e., a
site must be at the corners of its three label
squares. We obtain an optimal $\Theta(n \log n)$
time algorithm for the latter problem.}
}
@InProceedings{dtb-dgaga-99,
author = {Steven van Dijk and Dirk Thierens and Mark de Berg},
title = {On the Design of Genetic Algorithms for Geographical
Applications},
booktitle = {Proc. Genetic and Evolutionary
Computation Conf. (GECCO'99)},
year = 1999,
editor = {W. Banzhaf and J. Daida and A.E. Eiben and
M.H. Garzon and V. Honavar and M. Jakiela and
R.E. Smith},
month = jul,
publisher = {Morgan Kaufmann},
vol = 1,
pages = {188--195},
postscript = {http://www.cs.uu.nl/people/steven/download/gecco.ps.gz},
precedes = {dtb-segag-00},
succeeds = {dtb-rgahq-98}
}
@TechReport{dtb-rgahq-98,
author = {Steven van Dijk and Dirk Thierens and Mark de Berg},
title = {Robust genetic algorithms for high quality map labeling},
institution = UU,
number = {UU-CS-1998-41},
year = 1998,
pdf = {ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-1998/1998-41.pdf},
precedes = {dtb-segag-00, dtb-segag-00}
}
@InProceedings{dtb-segag-00,
author = {Steven van Dijk and Dirk Thierens and Mark de Berg},
title = {Scalability and Efficiency of Genetic Algorithms for
Geometrical Applications},
booktitle = {Proc. Parallel Problem Solving from Nature (PPSN VI)},
pages = {683--692},
year = 2000,
editor = {Marc Schoenauer and Kalyanmoy Deb and Gunter Rudolph
and Xin Yao and Evelyne Lutton and Juan Julian
Mercelo and Hans-Paul Schwefel},
volume = 1917,
series = LNCS,
location = {Paris},
month = sep,
publisher = SV,
postscript = {http://www.cs.uu.nl/people/steven/download/ppsnVI.ps.gz},
succeeds = {dtb-rgahq-98, dtb-dgaga-99},
precedes = {dtb-segag-00},
ISBN = 3540410562
}
@Misc{e-aclps-99,
author = {Evermap},
title = {Evername---an Advanced Cartographic
Label-Placement Software for {MapInfo Professional}},
howpublished = {\url{http://www.evermap.com/evername.htm}},
year = 1999,
url = {http://www.evermap.com/evername.htm}
}
@Misc{e-facnp-98,
Author = {ESRI},
title = {{MAPLEX}---a Fully Automated Cartographic
Name-Placement Software},
howpublished = {\url{http://www.esri.com/software/maplex/}},
year = 1998,
url = {http://www.esri.com/software/maplex/}
}
@Manual{e-macnp-98,
title = {Maplex---Automatic Cartographic Name Placement
Software},
organization = {ESRI},
year = 1998,
pdf = {http://www.esri.com/library/whitepapers/pdfs/maplexwp.pdf}
}
@InProceedings{e-npprm-85,
author = {J.R. Eastman},
title = {Names Placement and Positional Recall of Map
Information},
booktitle = {Proc. Auto-Carto 7, Digital Presentations of Spatial
Knowledge},
year = 1985,
pages = {474--482}
}
@Article{ecms-gcla-97,
author = {Shawn Edmondson and Jon Christensen and Joe Marks
and Stuart Shieber},
title = {A General Cartographic Labeling Algorithm},
journal = {Cartographica},
year = 1997,
volume = 33,
number = 4,
pages = {13--23},
pdf = {http://www.eecs.harvard.edu/\~{}shieber/Biblio/Papers/gen-label.pdf}
}
@InProceedings{eg-anpni-89,
author = {Leo R. Ebinger and Ann M. Goulette},
title = {Automated Name Placement in a Non-Interactive
Environment},
booktitle = {Proc. Auto-Carto 9},
year = 1989,
pages = {205--214},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-9/pdf/automated-names-placement-in-a-non-interactive-environment.pdf}
}
@Article{eg-nianp-90,
author = {Leo R. Ebinger and Ann M. Goulette},
title = {Noninteractive Automated Names Placement for the
1990 Decennial Census},
journal = {Cartography and GIS},
year = 1990,
volume = 17,
number = 1,
pages = {69--78}
}
@InProceedings{ehjmw-naalw-06,
author = {Thomas Erlebach and Torben Hagerup and Klaus Jansen
and Moritz Minzlaff and Alexander Wolff},
title = {A New Approximation Algorithm for Labeling Weighted
Points with Sliding Labels},
booktitle = {Proc. 22nd European Workshop
Comput. Geom. (EWCG'06)},
pages = {137--140},
year = 2006,
confmonth = {27--29~} # mar,
address = {Delphi},
pdf = AWPUBURL # {ehjmw-naalw-06.pdf},
cites = {aks-lpmis-98, m-bgpvl-05, pssuw-lpw-03, ksw-plsl-99,
ZZZ},
precedes = {ehjmw-tgapl-08}
}
@InProceedings{ehjmw-tgapl-08,
author = {Thomas Erlebach and Torben Hagerup and Klaus Jansen
and Moritz Minzlaff and Alexander Wolff},
title = {Trimming of Graphs, with an Application to Point
Labeling},
booktitle = {Proc. 25th Internat. Sympos. Theoretical Aspects
Comput. Sci. (STACS'08)},
pages = {265--276},
year = 2008,
editor = {Susanne Albers and Pascal Weil},
confmonth = {21--23~} # feb,
address = {Bordeaux},
pdf = AWPUBURL # {ehjmw-tgapl-08.pdf},
succedes = {ehjmw-naalw-06},
precedes = { }
}
@Article{ehjmw-tgapl-09,
author = {Thomas Erlebach and Torben Hagerup and Klaus Jansen
and Moritz Minzlaff and Alexander Wolff},
title = {Trimming of Graphs, with Application to Point
Labeling},
journal = TOCS,
year = 2009,
volume = { },
number = { },
pages = { },
doi = {10.1007/s00224-009-9184-8},
url = {http://dx.doi.org/10.1007/s00224-009-9184-8},
pdf = AWPUBURL # {ehjmw-tgapl-09.pdf},
keywords = {Trimming weighted graphs, domino treewidth, planar
graphs, layer bandwidth, point-feature label
placement, map labeling, sliding labels,
polynomial-time approximation schemes},
abstract = {For $t>0$ and $g\ge 0$, a vertex-weighted graph of
total weight $W$ is \emph{$(t,g)$-trimmable} if it
contains a vertex-induced subgraph of total weight
at least $(1-1/t)W$ and with no simple path of more
than $g$ edges. A family of graphs is
\emph{trimmable} if for every constant $t>0$, there
is a constant $g\ge 0$ such that every
vertex-weighted graph in the family is
$(t,g)$-trimmable. We show that every family of
graphs of bounded domino treewidth is trimmable.
This implies that every family of graphs of bounded
degree is trimmable if the graphs in the family have
bounded treewidth or are planar. We also show that
every family of directed graphs of bounded layer
bandwidth (a less restrictive condition than bounded
directed bandwidth) is trimmable. As an application
of these results, we derive polynomial-time
approximation schemes for various forms of the
problem of labeling a subset of given weighted point
features with nonoverlapping sliding axes-parallel
rectangular labels so as to maximize the total
weight of the labeled features, provided that the
ratios of label heights or the ratios of label
lengths are bounded by a constant. This settles one
of the last major open questions in the theory of
map labeling.},
note = {Appeared online at
\path|http://dx.doi.org/10.1007/s00224-009-9184-8|.},
succeeds = {ehjmw-tgapl-08}
}
@InProceedings{ejs-ptasg-01,
author = {Thomas Erlebach and Klaus Jansen and Eike Seidel},
title = {Polynomial-time approximation schemes for geometric
graphs},
booktitle = {Proc. 12th ACM-SIAM Sympos. on Discrete Algorithms
(SODA'01)},
year = 2001,
location = {Washington, DC},
month = {7--9~} # jan,
pages = {671--679},
cites = {aks-lpmis-98, b-aancp-94, ye-lrtaw-85, bls-gcs-99,
ccj-udg-90, dmmmz-mlg-97, dmm-pslsp-00, g-agtpg-80,
h-chan-96, h-oir-97, hmrrrs-ncasn-96, k-kka-36,
k-ignac-97, m-gtmfa-97, mbhrr-shudg-97, mm-tigt-99,
ksw-plsl-99, ws-mlb-96, ZZZ},
postscript = {http://www.tik.ee.ethz.ch/\~{}erlebach/soda2001.ps.gz}
}
@Article{ejs-ptasg-05,
author = {Thomas Erlebach and Klaus Jansen and Eike Seidel},
title = {Polynomial-Time Approximation Schemes for Geometric
Intersection Graphs},
journal = {SIAM J. Comput.},
volume = 34,
number = 6,
year = 2005,
pages = {1302--1323},
ee = {http://dx.doi.org/10.1137/S0097539702402676},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@TechReport{ekw-fblnm-03,
author = {Dietmar Ebner and Gunnar W. Klau and Ren{\'e}
Weiskircher},
title = {Force-Based Label Number Maximization},
institution = {Institut f{\"u}r Computergraphik und Algorithmen,
Technische Universit{\"a}t Wien},
year = 2003,
number = {TR-186-1-03-02},
month = jun,
pdf = {http://www.apm.tuwien.ac.at/publications/bib/pdf/ebner-03.pdf},
abstract = {We present a force-based simulated annealing
algorithm to heuristically solve the NP-hard label
number maximization problem LNM: Given a set of
rectangular labels, each of which belongs to a
point-feature in the plane, the task is to find a
labeling for a largest subset of the labels. A
labeling is a placement such that none of the labels
overlap and each is placed at its
point-feature. \par The abstraction of the problem
to the virtual force system allows us to implement
additional aesthetic criteria and to compute
placements with good label distribution in a short
amount of time. Furthermore, our algorithm can be
applied as a postprocessing step to improve existing
labelings. We find that the results often look
similar to those of a human cartographer. \par
Extensive computational experiments on widely used
benchmark data demonstrate that our new algorithm
produces solutions where the number of placed labels
is close to optimality and where the distribution of
the labels is better than in labelings computed by
algorithms that only maximize the number of placed
labels. The experiments also show that the algorithm
is able to solve large problems fast. This
demonstrates its applicability in dynamic real-time
environments, e.g., in navigation systems.}
}
@InProceedings{ekw-lnmit-05,
author = {Dietmar Ebner and Gunnar W. Klau and Ren{\'e}
Weiskircher},
title = {Label Number Maximization in the Slider Model},
booktitle = {Proc. 12th Internat. Symp. on Graph Drawing (GD'04)},
location = {New York},
pages = {144--154},
year = 2005,
confmonth = {29~} # sep # {~-- 2~} # oct,
editor = {J{\'a}nos Pach},
volume = 3383,
series = LNCS,
publisher = SV,
url = {http://dx.doi.org/10.1007/b105810},
doi = {10.1007/b105810}
}
@PhdThesis{f-agpsp-92,
author = {Michael Formann},
title = {Algorithms for Geometric Packing and Scaling
Problems},
school = FU,
year = 1992,
postscript = {http://www.inf.fu-berlin.de/inst/ag-ti/external/dissertationen/michaeleng.ps}
}
@InProceedings{f-algm-85,
author = {Herbert Freeman},
title = {The Automatic Labeling of Geographic Maps --- {A}
Problem in Computer Aesthetics},
booktitle = {Graphics Interface '85},
year = 1985,
month = may,
pages = {273--281},
}
@InCollection{f-alm-95,
author = {Herbert Freeman},
title = {On the Automated Labeling of Maps},
booktitle = {Shape, Structure and Pattern Recognition},
publisher = {World Scientific, Singapore},
year = 1995,
editor = {D. Dori and A. Bruckstein},
pages = {432--442},
update = {98.09 strijk}
}
@InCollection{f-cnp-91,
author = {Herbert Freeman},
title = {Computer Name Placement},
editor = {D.J. Maguire and M.F. Goodchild and D.W. Rhind},
booktitle = {Geographical Information Systems: Principles and
Applications},
publisher = {Longman},
address = {London},
year = 1991,
pages = {445--456},
update = {96.09 kreveld}
}
@Article{f-esapn-88,
author = {Herbert Freeman},
title = {An Expert System for the Automatic Placement of
Names on a Geographic Map},
journal = {Information Sciences},
year = 1988,
volume = 45,
pages = {367--378},
update = {98.01 wolff}
}
@Article{f-escd-93,
author = {D. Forrest},
title = {Expert Systems and Cartographic Design},
journal = {The Cartographic Journal},
year = 1993,
volume = 30,
pages = {143--148}
}
@Misc{f-maags-94,
author = {Mitchell Feigenbaum},
title = {Method and apparatus for automatically generating
symbol images against a background image without
collision utilizing distance-dependent attractive
and repulsive forces in a computer simulation},
howpublished = {U.S. Patent #5,355,314. Assigned to Hammond Inc.,
Maplewood, New Jersey. Patent filed 11/5/93,
received 10/11/94},
year = 1994
}
@InProceedings{f-mdpap-83,
author = {Herbert Freeman},
title = {Map Data Processing and the Annotation Problem},
booktitle = {Proc. 3rd Skandinavian Conf. Image Analysis},
year = 1983,
pages = {}
}
@Article{fa-ppngm-87,
author = {Herbert Freeman and John Ahn},
title = {On the Problem of Placing Names in a Geographic Map},
journal = {Internat. J. of Pattern Recog. and Art. Intell.},
year = 1987,
volume = 1,
number = 1,
pages = {121--140}
}
@InProceedings{flhass-almdu-06,
author = {Georg Fuchs and Martin Luboschik and Knut Hartmann
and Kamran Ali and Heidrun Schumann and Thomas
Strothotte},
title = {Adaptive Labeling on Mobile Devices using Remote
Service Infrastructures},
booktitle = {10th Internat.\ Conf. on Information Visualisation
(IV'06)},
pages = { },
address = {London, UK},
month = {5--7~} # jun,
publisher = {IEEE Computer Society},
year = 2006
}
@InProceedings{fmc-alssm-96,
author = {Herbert Freeman and Sean Marrinan and Hitesh
Chitalia},
title = {Automated Labeling of Soil Survey Maps},
booktitle = {Proc. ASPRS-ACSM Annual Convention, Baltimore},
year = 1996,
volume = 1,
pages = {51--59}
}
@TechReport{fp-eldnl-98,
author = {Jean-Daniel Fekete and Catharine Plaisant},
title = {Excentric Labeling: Dynamic Neighborhood Labeling
for Data Visualization},
institution = {Department of Computer Science, University of
Maryland},
year = 1998,
number = {CS-TR-3946, UMIACS-TR-98-59},
postscript = {ftp://ftp.cs.umd.edu/pub/papers/papers/ncstrl.umcp/CS-TR-3946/CS-TR-3946.ps.Z}
}
@InProceedings{fp-eldnl-99,
author = {Jean-Daniel Fekete and Catharine Plaisant},
title = {Excentric Labeling: Dynamic Neighborhood Labeling
for Data Visualization},
booktitle = {Proc. Conf. on Human Factors in Computer
Systems (CHI'99)},
pages = {512-519},
year = 1999,
location = {Pittsburgh, PA},
confmonth = {15--20~} # may,
publisher = {ACM New York},
url = {http://portal.acm.org/citation.cfm?id=302979.303148&dl=portal&dl=ACM&type=series&idx=SERIES260&part=Proceedings&WantType=Proceedings&title=Conference%20on%20Human%20Factors%20and%20Computing%20Systems},
pdf = {http://portal.acm.org/ft_gateway.cfm?id=303148&type=pdf&coll=GUIDE&dl=ACM&CFID=21536067&CFTOKEN=82550886},
abstract = {The widespread use of information visualization is
hampered by the lack of effective labeling
techniques. A taxonomy of labeling methods is
proposed. We then describe \emph{excentric labeling},
a new dynamic technique to label a neighborhood of
objects located around the cursor. This technique
does not intrude into the existing interaction, it
is not computationally intensive, and was easily
applied to several visualization applications. A
pilot study indicates a strong speed benefit for
tasks that involve the rapid exploration of large
numbers of objects.}
}
@Article{fpt-opcpa-81,
author = {Robert J. Fowler and Michael S. Paterson and Steven
L. Tanimoto},
title = {Optimal Packing and Covering in the Plane are
{NP}-Complete},
journal = IPL,
volume = 12,
number = 3,
year = 1981,
pages = {133--137}
}
@InProceedings{fpv-alafs-94,
author = {Herbert Freeman and Mehul Pandya and Aruna Vedula},
title = {Automatic Labeling of Area Features in Soil Survey
Maps},
booktitle = {Proc. 9th GRASS Conf.},
month = mar,
year = 1994,
pages = {}
}
@Misc{fw-eskml-93,
author = {Michael Formann and Frank Wagner},
title = {An Efficient Solution to {K}nuth's {METAFONT} Labeling
Problem},
howpublished = {Manuscript available at \url{http://i11www.ira.uka.de/map-labeling/papers/fw-eskml-93.ps.gz}},
year = 1993,
note = {Fachbereich Informatik, Freie Universit{\"a}t
Berlin},
postscript = MAPLABURL # {fw-eskml-93.ps.gz}
}
@InProceedings{fw-ppalm-91,
author = {Michael Formann and Frank Wagner},
title = {A Packing Problem with Applications to Lettering of
Maps},
booktitle = {Proc. 7th Annu. ACM Sympos. Comput. Geom. (SoCG'91)},
year = 1991,
pages = {281--288},
keywords = {packing, optimization},
cites = {b-lbact-83, e-ddsoi-80, eis-ctmfp-76, gj-cigtn-79,
ia-eaggs-86, i-pnm-75, y-laml-72, ZZZ},
update = {97.11 bibrelex}
}
@TechReport{fw-ppalm-91t,
author = {Michael Formann and Frank Wagner},
title = {A Packing Problem with Applications to Lettering of
Maps},
institution = FU,
year = 1991,
number = {B 91-04},
month = mar
}
@Article{g-anp-82,
author = {A. Greggains},
title = {Automated Name Placement},
journal = {Cartographica},
year = 1982,
volume = 19,
number = 2,
pages = {133--135}
}
@PhdThesis{g-citti-08,
author = {Timo G{\"o}tzelmann},
title = {Correlating Illustrations and Text through
Interactive Annotation},
school = {Institut für Simulation und Graphik, Universit{\"a}t
Magdeburg},
year = 2008,
month = feb,
publisher = {Verlag Dr.~M{\"u}ller},
isbn = {978-3836463607}
}
@MastersThesis{g-cnplf-96,
author = {Vasantha Gullapalli},
title = {Computerized Name Placement for the Line Features of
a Map},
school = {Department of Electrical and Computer Engineering,
Rutgers University},
year = 1996
}
@MastersThesis{g-ivib3-04,
author = {Timo G{\"o}tzelmann},
title = {{Interaktive Visualisierung interner Beschriftungen
in 3D-Oberflächenmodellen}},
school = {Fachhochschule Fulda, Fachbereich Angewandte
Informatik und Mathematik},
year = 2004
}
@Unpublished{g-snp-82,
author = {A. Greggains},
title = {A Strategy for Name Placement},
school = {University of Cambridge, Computer Laboratory},
year = 1982,
note = {Unpublished}
}
@InProceedings{gahs-ali-05,
author = {Timo G{\"o}tzelmann and Kamran Ali and Knut Hartmann
and Thomas Strothotte},
title = {Adaptive Labeling for Illustrations},
booktitle = {Proc.\ 13th Pacific Conf. Computer Graphics and
Applications},
pages = {64--66, 196},
editor = {E. Wu and D. Manocha and C. Gotsman},
location = {Macao, China},
month = {12--14~} # oct,
year = 2005
}
@InProceedings{gahs-fffai-05,
author = {Timo G{\"o}tzelmann and Kamran Ali and Knut Hartmann
and Thomas Strothotte},
title = {Form Follows Function: Aesthetic Interactive Labels},
booktitle = {Computational Aesthetics in Graphics, Visualization
and Imaging},
pages = { },
editor = {L. Neumann and M. Sbert and B. Gooch and
W. Purgathofer},
location = { },
publisher = {Eurographics Association},
year = 2005
}
@InProceedings{ggahs-pitcs-06,
author = {Timo G{\"o}tzelmann and Marcel G{\"o}tze and Kamran
Ali and Knut Hartmann and Thomas Strothotte},
title = {Practical Illustration of Texts: Customized Search,
View Selection, and Annotation},
booktitle = {{Mensch {\&} Computer: Mensch und Computer im
Strukturwandel}},
pages = { },
year = 2006
}
@InProceedings{ghs-aa3do-07,
author = {Timo G{\"o}tzelmann and Knut Hartmann and Thomas
Strothotte},
title = {Annotation of Animated 3D Objects},
booktitle = {Proc. 18th Conf. Simulation and Visualization
(SimVis'07)},
pages = { },
year = 2007,
location = {Madgeburg},
pdf = {http://www.simvis.org/Tagung2007/proceedings/4.4.pdf},
abstract = {This paper presents a novel approach to illustrate
dynamic procedures in tutoring materials by
analyzing corresponding animations. We propose two
strategies: (i) to enhance animations with secondary
elements (e.g., textual annotations and arrows) and
(ii) to generate visual summaries,
i.e. illustrations where secondary elements provide
indications of the direction and the extent of
moving objects in animations. We propose metrics
aiming at an unambiguous and frame-coherent layout
in animations. Moreover, we integrated real-time
algorithms to layout secondary elements in
animations into an interactive 3D browser. In order
to test the impact of various conflicting functional
and aesthetic layout requirements, our system
contains several algorithms and strategies, which
are compared in a user study. Finally, this paper
presents result of applying our approach to enhance
scientific illustrations and technical
documentation.}
}
@InProceedings{ghs-abai3-06,
author = {Timo G{\"o}tzelmann and Knut Hartmann and Thomas
Strothotte},
title = {Agent-Based Annotation of Interactive 3D
Visualizations},
booktitle = {6th Internat.\ Symp.\ on Smart Graphics},
editor = {A. Butz and B. Fisher and A. Kr{\"u}ger and P. Olivier},
month = {23--25~} # jul,
location = {Vancouver, Canada},
pages = { },
year = 2006
}
@InProceedings{ghs-cgl-06,
author = {Timo G{\"o}tzelmann and Knut Hartmann and Thomas
Strothotte},
title = {Contextual Grouping of Labels},
booktitle = {Simulation and Visualization},
editor = {T. Schulze and G. Horton and B. Preim and
S. Schlechtweg},
publisher = {Society for Computer Simulation Internat.},
address = {Erlangen},
year = 2006
}
@TechReport{ghs-la-05,
author = {Timo G{\"o}tzelmann and Knut Hartmann and Thomas
Strothotte},
title = {Labeling Agents},
institution = {Department of Computer Science, Otto-von-Guericke
University of Magdeburg},
number = {11/2005},
month = dec,
year = 2005
}
@InProceedings{gimprw-lsl-01,
author = {Mari {\'A}ngeles Garrido and Claudia Iturriaga and
Alberto M{\'a}rquez and Jos{\'e} Ramon Portillo and
Pedro Reyes and Alexander Wolff},
title = {Labeling Subway Lines},
booktitle = {Proc. 12th Annu. Internat. Sympos.
Algorithms Comput. (ISAAC'01)},
editor = {Peter Eades and Tadao Takaoka},
series = LNCS,
publisher = SV,
volume = 2223,
year = 2001,
pages = {649--659},
location = {Christchurch},
confmonth = {19--21~} # dec,
url = {http://link.springer.de/link/service/series/0558/bibs/2223/22230649.htm},
pdf = AWPUBURL # {gimprw-lsl-01.pdf},
cites = {af-aesam-84, bd-mpatm-00, cbdks-srn-01, c-cgitf-99,
cms-esapf-95, dmm-pslsp-00, fw-ppalm-91,
gj-cigtn-79, h-aanpa-82, il-elapm-99, ksy-lrmsl-01,
pssw-lpw-01i, qwxz-na2lp-00, ksw-plsl-99, ws-mlb-96,
ZZZ},
succedes = {gmiprw-epa-01},
abstract = {Graphical features on map, charts, diagrams and
graph drawings usually must be annotated with text
labels in order to convey their meaning. In this
paper we focus on a problem that arises when
labeling schematized maps, e.g. for subway
networks. We present algorithms for labeling points
on a line with axis-parallel rectangular labels of
equal height. Our aim is to maximize label size
under the constraint that all points must be
labeled. Even a seemingly strong simplification of
the general point-labeling problem, namely to decide
whether a set of points on a horizontal line can be
labeled with sliding rectangular labels, turns out
to be weakly NP-complete. This is the first labeling
problem that is known to belong to this class. We
give a pseudo-polynomial time algorithm for it. In
case of a sloping line points can be labeled with
maximum-size square labels in $O(n \log n)$ time if
four label positions per point are allowed and in
$O(n^3\log n)$ time if labels can slide. We also
investigate rectangular labels.}
}
@InProceedings{gmiprw-epa-01,
author = {Mari {\'A}ngeles Garrido and Alberto M{\'a}rquez and
Claudia Iturriaga and Jos{\'e} Ramon Portillo and
Pedro Reyes and Alexander Wolff},
title = {Etiquetado de puntos alineados},
booktitle = {Proc. IX Encuentros de Geometr{\'i}a Computacional
(EGC'01)},
pages = {285--294},
year = 2001,
month = {2--4~} # jul,
location = {Girona},
postscript = AWPUBURL # {gmiprw-epa-01.ps.gz},
precedes = {gimprw-lsl-01},
language = {spanish}
}
@Article{h-aanpa-82,
author = {Stephen A. Hirsch},
title = {An Algorithm for Automatic Name Placement Around
Point Data},
journal = {The American Cartographer},
year = 1982,
volume = 9,
number = 1,
pages = {5--17},
update = {98.01 strijk}
}
@MastersThesis{h-aappd-80,
author = {Stephen A. Hirsch},
title = {An Algorithm for Automated Placement of Point Data},
school = {Department of Geography, State University of New
York at Buffalo, New York},
year = 1980
}
@Article{h-lmbi-66,
author = {A.G. Hodgkiss},
title = {Lettering Maps for Book Illustration},
journal = {The Cartographer},
year = 1966,
volume = 3,
pages = {42--46}
}
@MastersThesis{h-vrdsb-98,
author = {Markus Heber},
title = {{V}orausberechnung reaktiver {D}atenstrukturen zur
schnellen {B}eschriftung von {L}andkarten},
school = {Institut f{\"u}r Informatik III, Universit{\"a}t Bonn},
month = feb,
year = 1998,
language = {german},
url = {http://www.ikg.uni-bonn.de/Publikationen/Diplomarbeiten/markus_heber.zip}
}
@InProceedings{has-fladp-04,
author = {Knut Hartmann and Kamran Ali and Thomas Strothotte},
title = {Floating Labels: Applying Dynamic Potential Fields
for Label Layout},
booktitle = {Proc. 4th Internat.\ Symp.\ on Smart Graphics},
pages = {101--113},
editor = {Andreas Butz and Antonio Kr{\"u}ger and Patrick
Olivier},
location = {Banff, Canada},
month = {23--25~} # may,
publisher = SV,
series = LNCS,
volume = 3031,
year = 2004
}
@TechReport{hd-dmwfe-05,
author = {Horst Hering and Alain Duverger},
title = {Development of a Mathematical weighted Formula to
eliminate the overlapping of Aircraft Labels on the
{ATC} Radar Display},
institution = {Eurocontrol Experimental Centre},
year = 2005,
month = sep,
number = 028,
url = {http://www.eurocontrol.int/eec/public/standard_page/DOC_Report_2005_028.html},
pdf = {http://www.eurocontrol.int/eec/gallery/content/public/document/eec/report/2005/028_Eliminate_Overlapping_Aircraft_Labels.pdf}
}
@InProceedings{hg-diinp-82,
author = {Stephen A. Hirsch and Barry J. Glick},
title = {Design Issues for an Intelligent Names Processing
System},
booktitle = {Proc. Auto-Carto 5},
year = 1982,
pages = {337--346},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-5/pdf/design-issues-for-an-intelligent-names-processing-system.pdf}
}
@InProceedings{hgas-mfall-05,
author = {Knut Hartmann and Timo G{\"o}tzelmann and Kamran Ali
and Thomas Strothotte},
title = {Metrics for Functional and Aesthetic Label Layouts},
booktitle = {Proc. 5th Internat.\ Symp.\ on Smart Graphics},
pages = {115--126},
editor = {Andreas Butz and B. Fisher and Antonio Kr{\"u}ger
and Patrick Olivier},
series = LNCS,
volume = 3638,
publisher = SV,
month = {22--24~} # may,
location = {Frauenw{\"o}rth Cloister, Germany},
year = 2005
}
@Article{hm-ascpp-85,
author = {Dorit S. Hochbaum and Wolfgang Maass},
title = {Approximation Schemes for Covering and Packing
Problems in Image Processing and {VLSI}},
journal = JACM,
year = 1985,
volume = 32,
pages = {130--136}
}
@InProceedings{hmrrrs-uaasn-94,
author = {Harry B. {Hunt III} and Madhav V. Marathe and
Venkatesh Radhakrishnan and S.S. Ravi and Daniel
J. Rosenkrantz and Richard E. Stearns},
title = {A Unified Approach to Approximation Schemes for
{NP}- and {PSPACE}-Hard Problems for Geometric
Graphs},
booktitle = {Proc. 2nd Annu. European Sympos. Algorithms
(ESA'94)},
series = LNCS,
publisher = SV,
volume = 855,
year = 1994,
pages = {424--435},
update = {97.03 kreveld}
}
@InProceedings{hskl-ailrt-05,
author = {Lars Harrie and Hanna Stigmar and Tommi Koivula and
Lassi Lehto},
title = {An Algorithm for Icon Labelling on a Real-Time Map},
booktitle = {Proc. 11th Internat. Symp. Spatial Data Handling
(SDH'05)},
pages = {493-507},
year = 2005,
editor = {Peter F. Fisher},
doi = {10.1007/3-540-26772-7_38}
}
@InProceedings{i-ank-62,
author = {Eduard Imhof},
title = {{Die Anordnung der Namen in der Karte}},
booktitle = {Internat. Yearbook of Cartography},
publisher = {Kirschbaum},
location = {Bonn Bad Godesberg},
language = {german},
year = 1962,
pages = {93--129}
}
@TechReport{i-anpac-94,
author = {Itzhak Pinto},
title = {Area Name Placement for Automated Cartography},
institution = {Department of Electrical and Computer Engineering,
Rutgers University, Piscataway, NJ 08855-0909},
year = 1994,
number = {CE-104}
}
@Article{i-fccig-82,
author = {Hiroshi Imai},
title = {Finding Connected Components of an Intersection
Graph of Squares in the Euclidian Plane},
journal = IPL,
year = 1982,
volume = 15,
number = 3,
pages = {125--128}
}
@PhdThesis{i-mlp-99,
author = {Claudia Iturriaga},
title = {Map Labeling Problems},
school = {School of Computer Science, University of Waterloo},
year = 1999,
url = {http://www.cs.unb.ca/profs/citurria/Research/},
postscript = {http://www.cs.unb.ca/profs/citurria/Research/final-thesis.ps}
}
@Article{i-pnm-75,
author = {Eduard Imhof},
title = {Positioning Names on Maps},
journal = {The American Cartographer},
volume = 2,
number = 2,
year = 1975,
pages = {128--144},
update = {97.11 kreveld, wolff}
}
@Article{ia-eaggs-86,
author = {Hiroshi Imai and Takao Asano},
title = {Efficient Algorithms for Geometric Graph Search
Problems},
journal = {SIAM Journal on Computing},
volume = 15,
number = 2,
year = 1986,
pages = {478--494},
keywords = {intersection, dynamizing, data structuring,
searching, VLSI design, decomposition, amortized
analysis},
update = {97.11 bibrelex}
}
@Article{ia-fccmc-83,
author = {Hiroshi Imai and Takao Asano},
title = {Finding the Connected Components and a Maximum
Clique of an Intersection Graph of Rectangles in the
Plane},
journal = {Journal on Algorithms},
volume = 4,
year = 1983,
pages = {310--323},
keywords = {VLSI design, plane sweep, rectangles, intersection}
}
@Article{il-elapm-03,
author = {Claudia Iturriaga and Anna Lubiw},
title = {Elastic Labels Around the Perimeter of a Map},
journal = JA,
year = 2003,
volume = 47,
number = 1,
pages = {14--39}
}
@InProceedings{il-elapm-98,
author = {Claudia Iturriaga and Anna Lubiw},
title = {Elastic Labels on the Perimeter of a Rectangle},
booktitle = {Proc. Symp. 6th Internat. Symp. on Graph Drawing (GD'98)},
editor = {Sue H. Whitesides},
series = LNCS,
publisher = SV,
volume = 1547,
pages = {452--453},
year = 1998,
month = {13--15~} # aug,
url = {http://link.springer.de/link/service/series/0558/tocs/t1547.htm}
}
@InProceedings{il-elapm-99,
author = {Claudia Iturriaga and Anna Lubiw},
title = {Elastic Labels Around the Perimeter of a Map},
booktitle = {Proc. 8th Internat. Workshop on
Algorithms and Data Structures (WADS'99)},
location = {Vancouver, B.C., Canada},
series = LNCS,
publisher = SV,
volume = 1663,
pages = {306--317},
year = 1999,
month = {12--14~} # aug
}
@InProceedings{il-eltac-97,
author = {Claudia Iturriaga and Anna Lubiw},
title = {Elastic Labels: The Two-Axis Case},
booktitle = {Proc. Symp. 5th Internat. Symp. on Graph Drawing (GD'97)},
location = {Rome, Italy},
series = LNCS,
publisher = SV,
volume = 1353,
month = {18--20~} # sep,
year = 1997,
pages = {181--192},
url = {http://www.cs.unb.ca/profs/citurria/Research/},
postscript = {http://www.cs.unb.ca/profs/citurria/Research/gd97.ps}
}
@TechReport{il-nhsml-97,
author = {Claudia Iturriaga and Anna Lubiw},
title = {{NP}-Hardness of Some Map Labeling Problems},
institution = {University of Waterloo, Canada},
year = 1997,
number = {CS-97-18},
url = {ftp://cs-archive.uwaterloo.ca/cs-archive/CS-97-18/},
postscript = {ftp://cs-archive.uwaterloo.ca/cs-archive/CS-97-18/np-hardness.ps.Z}
}
@PhdThesis{j-alpp-04,
author = {Joo-Won Jung},
title = {Automatic Label Placement on Points},
school = {Department of Electrical Engineering and Computer
Science, Korean Advanced Institute of Science and
Technology},
year = 2004,
month = nov
}
@Article{j-cnpp-89,
author = {Christopher Jones},
title = {Cartographic Name Placement with {P}rolog},
journal = {IEEE Computer Graphics \& Applications},
year = 1989,
volume = 9,
number = 5,
pages = {36--47}
}
@Article{j-crcnp-90,
author = {Christopher B. Jones},
title = {Conflict Resolution in Cartographic Name Placement
with {P}rolog},
journal = {Computer Aided Design},
year = 1990,
volume = 22,
number = 3,
pages = {173--183}
}
@PhdThesis{j-mlc-05,
author = {Minghui Jiang},
title = {Map Labeling with Circles},
school = {Department of Computer Science, Montana State
University},
year = 2005,
month = apr,
url = {http://www.montana.edu/etd/available/jiang_0505.html},
pdf = {http://www.montana.edu/etd/available/unrestricted/Jiang_0505.pdf},
abstract = {We study two geometric optimization problems
motivated by cartographic applications: Map Labeling
with Uniform Circles (MLUC) and Map Labeling with
Uniform Circle Pairs (MLUCP). We show that the
decision problems of both MLUC and MLUCP are
NP-hard, and that the related optimization problems
for maximizing the label sizes are NP-hard to
approximate within factor 1.0349. We design
approximation algorithms with constant performance
guarantees for the two problems: for MLUC, we
present a $(3+o)$-approximation and a
$(2.98+o)$-approximation; for MLUCP, a
$(1.5+o)$-approximation and a
$(1.491+o)$-approximation. We also describe the
implementation of AMLUC, a software system for
automated map labeling with uniform circles. The
system is based on our approximation algorithms for
MLUC and uses an effective shake-and-grow heuristic
to find near-optimal label placements.}
}
@Article{j-naalp-06,
author = {Minghui Jiang},
title = {A new approximation algorithm for labeling points
with circle pairs},
journal = IPL,
year = 2006,
volume = 99,
number = 4,
pages = {125--129}
}
@Article{j-nmpn-96,
author = {Peter Jolly},
title = {Naming Places, Placing Names},
journal = {Mapping Awareness},
year = 1996,
volume = 10,
pages = {28--30}
}
@InProceedings{jb-uaiap-89,
author = {David S. Johnson and Umit Basoglu},
title = {The Use of Artificial Intelligence in the Automated
Placement of Cartographic Names},
booktitle = {Proc. Auto-Carto 9},
year = 1989,
pages = {225--230},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-9/pdf/the-use-of-artifical-intelligence-in-the-automated-placement-of-cartographic-names.pdf}
}
@InProceedings{jbqz-nbmlc-04,
author = {Minghui Jiang and Sergey Bereg and Zhongping Qin
and Binhai Zhu},
title = {New bounds on map labeling with circular labels},
booktitle = {Proc. 15th Annu. Internat. Sympos.
Algorithms Comput. (ISAAC'04)},
pages = {606--617},
year = 2004,
editor = {Rudolf Fleischer and Gerhard Trippen},
volume = 3341,
series = LNCS,
location = {Hong Kong},
confmonth = {20--22~} # dec,
publisher = SV,
url = {http://springerlink.metapress.com/link.asp?id=qafvaakhqlm29ewn},
url2 = {http://link.springer.de/link/service/series/0558/bibs/3341/33410606.htm},
abstract = {We present new approximation algorithms for the
NP-hard problems of labeling points with
maximum-size uniform circles and circle pairs (MLUC
and MLUCP). Our algorithms build on the important
concept of maximal feasible region and new
algorithmic techniques. We obtain several results: a
$(2.98 + \epsilon)$-approximation for MLUC,
improving previous factor $3.0 + \epsilon$; a
$(1.491 + \epsilon)$-approximation for MLUCP,
improving previous factor 1.5; and the first
non-trivial lower bound 1.0349 for both MLUC and
MLUCP, improving previous lower bound $1+O(1/n)$.},
succeeds = {jqqzc-sf3al-03, wtx-sf23a-02}
}
@TechReport{jc-lpgr-03,
author = {Joo-Won Jung and Kyung-Yong Chwa},
title = {Labeling Points with Given Rectangles},
institution = {Korea Advanced Institute of Science and Technology
(KAIST)},
year = 2003,
pdf = {http://tclab.kaist.ac.kr/\~{}jwjung/papers/jc-lpgr-04.pdf},
abstract = {In this paper, we consider the following problem:
Given n pairs of a point and an axis-parallel
rectangle in the plane, place each rectangle at each
point in order that the point lies on the corner of
the rectangle and the rectangles do not
intersect. If the size of the rectangles may be
enlarged or reduced at the same factor, maximize the
factor. This paper generalizes the results of
Formann and Wagner \cite{fw-ppalm-91}. They
considered the uniform squares case and showed that
there is no polynomial time algorithm less than
2-approximation. We present a 2-approximation
algorithm of the non-uniform rectangle case which
runs in $O(n^2 log n)$ time and takes $O(n^2)$
space. We also show that the decision problem can be
solved in $O(n log n)$ time and space in the RAM
model by transforming the problem to a simpler
geometric problem.}
}
@Article{jc-lpgr-04,
author = {Joo-Won Jung and Kyung-Yong Chwa},
title = {Labeling points with given rectangles},
journal = IPL,
volume = 89,
number = 3,
year = 2004,
issn = {0020-0190},
pages = {115--121},
url = {http://dx.doi.org/10.1016/j.ipl.2003.09.017}
}
@InProceedings{jc-rbnpp-89,
author = {Christopher B. Jones and Anthony C. Cook},
title = {Rule-Based Name Placement with {P}ROLOG},
booktitle = {Proc. Auto-Carto 9},
year = 1989,
pages = {231--240},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-9/pdf/rule-based-cartographic-name-placement-with-prolog.pdf}
}
@InCollection{jcm-rbcan-91,
author = {Christopher B. Jones and Anthony C. Cook and
J.E. McBride},
title = {Rule-based control of automated name placement},
booktitle = {Mapping the Nations},
publisher = {Internat. Cartographic Association},
year = 1991,
volume = 1
}
@Article{jqqzc-sf3al-03,
author = {Minguhui Jiang and Jianbo Qian and Zhongping Qin and
Binhai Zhu and Robert Cimikowski},
title = {A simple factor-$3$ approximation for labeling
points with circles},
journal = IPL,
year = 2003,
volume = 87,
number = 2,
pages = {101--105},
url = {http://dx.doi.org/10.1016/S0020-0190(03)00256-4},
cites = {dlss-sdakp-95, dmm-pslsp-02, dmmmz-mlg-97,
ee-innfm-94, ps-cg-85, sw-lpc-01}
}
@MastersThesis{k-apfnm-80,
author = {P.C. Kelly},
title = {Automated Positioning of Feature Names on Maps},
school = {Department of Geography, State University of New
York at Buffalo, Buffalo, New York},
year = 1980
}
@MastersThesis{k-bl-98,
author = {Lars Knipping},
title = {{Beschriftung von Linienz{\"u}gen}},
school = FU,
year = 1998,
month = nov,
language = {german},
postscript = MAPLABURL # {k-bl-98.ps.gz}
}
@PhdThesis{k-caopp-01,
author = {Gunnar W. Klau},
title = {A Combinatorial Approach to Orthogonal Placement
Problems},
school = {Naturwissenschaftlich-Technische Fakult{\"a} I,
Universit{\"a}t des Saarlandes, Saarbr{\"u}cken},
year = 2001,
month = sep,
pdf = {http://www.apm.tuwien.ac.at/people/gunnar/pubs/Kla01.pdf},
abstract = {We study two families of NP-hard orthogonal
placement problems that arise in the area of
information visualization both from a theoretical
and a practical point of view. This thesis contains
a common combinatorial framework for compaction
problems in orthogonal graph drawing and for
point-feature labeling problems in computational
cartography. Compaction problems are concerned with
performing the conversion from a dimensionless
description of the orthogonal shape of a graph to an
area-efficient drawing in the orthogonal grid with
short edges. The second family of problems deals
with the task of attaching rectangular labels to
point-features such as cities or mountain peaks on a
map so that the placement results in a legible
map. We present new combinatorial formulations for
these problems employing a path- and cycle-based
graph-theoretic property in an associated
problem-specific pair of constraint graphs. The
refomulation allows us to develop exact algorithms
for the original problems. Extensive computational
studies on real-world benchmarks show that our
linear programming--based algorithms are able to
solve large instances of the placement problems to
provable optimality within short computation
time. Furthermore, we show how to combine the
formulations for compaction and labeling problems
and present an exact algorithmic approach for a
graph labeling problem. Often, our new algorithms
are the first exact algorithms for the respective
problem variant.}
}
@Unpublished{k-hplps-91,
author = {Warren F. Kuhfeld},
title = {A Heuristic Procedure for Label Placement in Scatterplots},
year = 1991
}
@Misc{k-lflpa-97,
author = {Joshua C. Kramer},
title = {Line Feature Label Placement for {ALPS5.0}},
school = {Rutgers University, Piscataway, NJ},
howpublished = {unpublished manuscript, available at \url{http://paul.rutgers.edu/~jckramer/academics/Report/}},
year = 1997,
url = {http://paul.rutgers.edu/\~{}jckramer/academics/Report/},
postscript = {http://paul.rutgers.edu/~{}jckramer/academics/Report/ReportBody.ps}
}
@Article{k-lpdo-03,
author = {Thomas K{\"a}mpke},
title = {Label placement for dynamic objects},
journal = {Machine Graphics \& Vision Internat. Journal},
year = 2003,
volume = 12,
number = 2,
pages = {215--234},
abstract = {Placing object labels in dynamic scenes requires the
label positions themselves to be dynamic. Algorithms
for dynamic label placement are presented that tend
to avoid overlaps and consider aesthetic
preferences. The procedures are derived from a
quadratic program. As a special feature, hysteresis
is incorporated to restrict the optical flow induced
by label changes.}
}
@Article{k-mnpm-86,
author = {Warren F. Kuhfeld},
title = {Metric and Nonmetric Plotting Models},
journal = {Psychometrika},
year = 1986,
volume = 51,
pages = {155--161}
}
@TechReport{k-pfnph-98,
author = {Jyothi Kashi},
title = {Point Feature Name Placement on High Density Maps
with Line Feature Interactions},
institution = {Department of Electrical and Computer Enginering,
Rutgers University, Piscataway, NJ},
year = 1998
}
@PhdThesis{k-psk-94,
author = {Wolfgang Kresse},
title = {{Plazierung von Schrift in Karten}},
school = {Hohe Landwirtschaftliche Fakult{\"a}t der
Rheinischen Friedrich-Wilhelms-Universit{\"a}t},
year = 1994,
address = {Bonn},
month = may,
language = {german},
note = {Available as volume~23 of the preprint series of the
Institute of Cartography and Geoinformation},
}
@Article{k-sa-95,
author = {Wolfgang Kresse},
title = {{Schriftplazierung in ATKIS}},
journal = {Nachrichten aus dem Karten- und Vermessungswesen},
series = {I},
year = 1995,
number = 113,
pages = {147--154},
publisher = {Verlag des Instituts f{\"u}r Angewandte Geod{\"a}sie},
address = {Frankfurt am Main},
language = {german},
abstract = {An urgent need for automatic map name placement has
evolved since the geo information system ATKIS was
introduced in a variety of ways in practical
application. As a research project at the Institute
for Cartography and Topography of the University of
Bonn a concept for automatic map name placement has
been developed and tested by means of a prototype
software. The rule-based method uses a digital map,
names and other parameters as input data to derive
the final positions of all annotations. As a
geometrical reference the name placement requires a
completely symbolized map, the so-called DKM
(Digitales Kartographisches Modell) in the essence
of ATKIS. The ATKIS-Signaturenkatalog (ATKIS-SK,
ATKIS symbolization catalogue) comprises
approximately 150 object codes which may be combined
with annotations.}
}
@Article{ki-eplp-01,
author = {Takayuki Kameda and Keiko Imai},
title = {Experimental performances for labeling problems},
journal = {IPSJ SIG Notes},
year = 2001,
number = 7,
pages = {59--64},
language = {japanese},
note = {In Japanese}
}
@Article{ki-mlppc-03,
author = {Takayuki Kameda and Keiko Imai},
title = {Map Label Placement for Points and Curves},
journal = {IEICE Trans. Fundamentals of Electronics,
Communications \& Comput. Sci.},
year = 2003,
volume = {E86--A},
number = 4,
pages = {835--840},
month = apr,
pdf = {http://www.ise.chuo-u.ac.jp/ise-labs/imai-lab/profile/klist/e86-a_4_835.pdf},
keywords = {label placement problem, geographic information
system, computational geometry, train map}
}
@Article{ki-nlppl-01,
author = {Yoshihito Ohtsuka and Keiko Imai},
title = {Node label placement problems with leader lines},
journal = {IPSJ SIG Notes},
year = 2001,
number = 7,
pages = {53--58},
language = {japanese},
note = {In Japanese}
}
@InProceedings{ki-npccp-88,
author = {T. Kato and H. Imai},
title = {The {NP}-Completeness of the Character Placement
Problem of 2 or 3 degrees of freedom},
booktitle = {Record of Joint Conf. of Electrical and
Electronic Engineers in Kyushu},
year = 1988,
pages = 1138,
language = {japanese},
note = {In Japanese},
update = {98.01 wolff}
}
@InProceedings{kly-mt1bl-07,
author = {Hao-Jen Kao, Chun-Cheng Lin, Hsu-Chen Yen},
title = {Many-to-one boundary labeling},
booktitle = {Proc. Asia-Pacific IEEE Sympos. on Visualisation
(APVIS'07)},
pages = {65--72},
year = 2007,
location = {Sydney},
confmonth = feb
}
@InCollection{km-allsd-03,
author = {Gunnar W. Klau and Petra Mutzel},
title = {Automatic Layout and Labelling of State Diagrams},
booktitle = {Mathematics---Key Technology for the Future},
editor = {W. J{\"a}ger and H.-J. Krebs},
pages = {584--608},
publisher = SV,
year = 2003,
address = {Berlin},
url = {http://www.apm.tuwien.ac.at/\~{}guwek/gunnar/KM00c.html},
pdf = {http://www.apm.tuwien.ac.at/people/gunnar/pubs/KM00c.pdf}
}
@InProceedings{km-cglc-99,
author = {Gunnar W. Klau and Petra Mutzel},
title = {Combining Graph Labeling and Compaction},
booktitle = {Proc. Symp. 7th Internat. Symp. on Graph Drawing (GD'99)},
series = LNCS,
publisher = SV,
volume = 1731,
year = 1999,
pages = {27--37},
ISSN = {0302-9743},
location = {{\v S}ti{\v r}{\'i}n Castle},
month = {15--19~} # sep,
url = {http://link.springer-ny.com/link/service/series/0558/bibs/1731/17310027.htm},
pdf = {http://link.springer-ny.com/link/service/series/0558/papers/1731/17310027.pdf},
abstract = {Combinations of graph drawing and map labeling
problems yield challenging mathematical problems and
have direct applications, e.g., in automation
engineering. We call graph drawing problems in which
subsets of vertices and edges need to be labeled
graph labeling problems. Unlike in map labeling
where the position of the objects is specified in
the input, the coordinates of vertices and edges in
a graph labeling problem instance have yet to be
determined and thus create additional degrees of
freedom. We concentrate on the Compaction and
Labeling (COLA) Problem: Given an orthogonal
representation---as produced by algorithms within the
topology-shape-metrics paradigm---and some label
information, the task is to generate a labeled
orthogonal embedding with minimum total edge
length. We characterize feasible solutions of the
COLA problem extending an existing framework for
solving pure compaction problems. Based on the
graph-theoretical characterization, we present a
branch-and-cut algorithm which computes optimally
labeled orthogonal drawings for given instances of
the COLA problem. First computational experiments on
a benchmark set of practical instances show that our
method is superior to the traditional approach of
applying map labeling algorithms to graph
drawings. To our knowledge, this is the first
algorithm especially designed to solve graph
labeling problems.}
}
@Article{km-olpfr-03,
author = {Gunnar W. Klau and Petra Mutzel},
title = {Optimal Labeling of Point Features in Rectangular
Labeling Models},
journal = {Mathematical Programming (Series B)},
year = 2003,
pages = {435--458},
postscript = { },
pdf = { },
succeeds = {km-olpfs-00}
}
@InProceedings{km-olpfs-00,
author = {Gunnar W. Klau and Petra Mutzel},
title = {Optimal Labelling of Point Features in the Slider
Model},
booktitle = {Proc. 6th Annual Internat. Computing and
Combinatorics Conf. (COCOON'00)},
editor = {D.-Z. Du and P. Eades and V. Estivill-Castro and
X. Lin and A. Sharma},
year = 2000,
series = LNCS,
volume = 1858,
location = {Sydney},
month = {26--28~} # jul,
publisher = SV,
pages = {340--350},
precedes = {km-olpfr-02},
url = {http://link.springer.de/link/service/series/0558/bibs/1858/18580340.htm},
postscript = {http://www.apm.tuwien.ac.at/\~{}guwek/gunnar/pubs/KM00a.ps},
pdf = {http://link.springer.de/link/service/series/0558/papers/1858/18580340.pdf},
abstract = {We investigate the label number maximisation problem
(LNM): Given a set of labels $\Lambda$, each of
which belongs to a point feature in the plane, the
task is to find a largest subset $\Lambda_P$ of
$\Lambda$ so that each $\lambda \in \Lambda_P$
labels the corresponding point feature and no two
labels from $\Lambda_P$ overlap. \par Our approach
is based on two so-called constraint graphs, which
code horizontal and vertical positioning
relations. The key idea is to link the two graphs by
a set of additional constraints, thus characterising
all feasible solutions of LNM. This enables us to
formulate a zero-one integer linear program whose
solution leads to an optimal labelling. \par We can
express LNM in both the discrete and the slider
labelling model. The slider model allows a
continuous movement of a label around its point
feature, leading to a significantly higher number of
labels that can be placed. To our knowledge, we
present the first algorithm that computes provably
optimal solutions in the slider model. First
experimental results on instances created by a
widely used benchmark generator indicate that the
new approach is applicable in practice.}
}
@InProceedings{kmik-peanp-91,
author = {Nobuhiko Kojiro and Ken'ichi Miura and Hiroshi Imai
and Yahiko Kambayashi},
title = {Performance Evaluation of Automatic Name Placement
Functions for Geographical Information Systems},
booktitle = {Proc. 2nd Internat. Sympos. on
Database Systems for Advanced Applications
(DASFAA'91)},
year = 1991,
pages = {491--497},
update = {98.04 strijk}
}
@InProceedings{kmp-artp-98,
author = {Sanjeev Khanna and S. Muthukrishnan and Mike
Paterson},
title = {On Approximating Rectangle Tiling and Packing},
pages = {384--393},
booktitle = {Proc. 9th Annual ACM-SIAM Sympos.
on Discretre Algorithms (SODA'98)},
month = jan,
year = 1998,
publisher = {ACM Press},
location = {New York}
}
@TechReport{kmp-artp-98t,
author = {Sanjeev Khanna and S. Muthukrishnan and Mike
Paterson},
title = {On Approximating Rectangle Tiling and Packing},
number = {CS-RR-339},
year = 1998,
month = mar,
type = {Research Report},
url = {http://www.dcs.warwick.ac.uk/pub/reports/rr/339.html},
postscript = {ftp://ftp.dcs.warwick.ac.uk/pub/reports/rr/339/all.ps.Z},
institution = {Department of Computer Science, University of
Warwick},
address = {Coventry, UK}
}
@InProceedings{kmps-eagpp-93,
author = {Ludek Ku{\v c}era and Kurt Mehlhorn and Bettina
Preis and Erik Schwarzenecker},
title = {Exact Algorithms for a Geometric Packing Problem},
booktitle = {Proc. 10th Sympos. on Theoretical Aspects in
Computer Science (STACS'93)},
series = LNCS,
volume = 665,
publisher = SV,
year = 1993,
pages = {317--322},
update = {93.05 smid}
}
@Article{kr-pcr-92,
author = {Donald E. Knuth and Arvind Raghunathan},
title = {The Problem of Compatible Representatives},
journal = {SIAM J. Discr. Math.},
year = 1992,
volume = 5,
number = 3,
pages = {422--427}
}
@InProceedings{ksw-apdm-04,
author = {Marc van Kreveld and {\'E}tienne Schramm and
Alexander Wolff},
title = {Algorithms for the Placement of Diagrams on Maps},
booktitle = {Proc. 12th Internat. Symp. ACM GIS (GIS'04)},
pages = {222--231},
year = 2004,
editor = {Dieter Pfoder and Isabel F. Cruz and Marc Ronthaler},
location = {Washington D.C.},
month = {12--13~} # nov,
pdf = AWPUBURL # {ksw-apdm-04.pdf},
keywords = {Placement algorithms, cartographic visualization},
abstract = {This paper discusses a variety of ways to place
diagrams like pie charts on maps, in particular,
administrative subdivisions. The different ways come
from different models of the placement problem: a
diagram of one region should cover other regions,
roads or boundaries as little as possible. In total
we present six models for diagram placement. We
outline three different algorithmic approaches and
discuss the efficiency of each approach for the
different models, and also for different types of
diagrams (rectangular, circular, same or different
sizes). We have implemented an algorithm for each
model and show the resulting diagram placements on a
number of maps. Our evaluation gives a first
indication which model is best for aesthetically
good diagram placement.},
cites = {aes-vdsl3-99, ak-dnpfi-91, bo-arcgi-79, ce-oails-92,
bkos-cgaa-00, d-ctmd-99, ecms-gcla-97, g-mva-96,
h-a-04, zh-rtmlp-04, h-fuenl-89, m-cgitr-93,
o-rourke, o-cgc-95, pf-facat-96, rmmkp-ec-95,
ft-pc-04, r-alclb-89, ws-mlb-96, ZZZ}
}
@Article{ksw-plsl-99,
author = {Marc van Kreveld and Tycho Strijk and Alexander
Wolff},
title = {Point Labeling with Sliding Labels},
journal = CGTA,
year = 1999,
volume = 13,
pages = {21--47},
pdf = AWPUBURL # {ksw-plsl-99.pdf},
update = {99.06 wolff}
}
@InProceedings{ksw-pslsl-98,
author = {Marc van Kreveld and Tycho Strijk and Alexander
Wolff},
title = {Point Set Labeling with Sliding Labels},
booktitle = {Proc. 14th Annu. ACM Sympos. Comput. Geom. (SoCG'98)},
year = 1998,
month = {7--10~} # jun,
location = {Minneapolis},
pages = {337--346},
postscript = AWPUBURL # {ksw-pslsl-98.ps.gz},
abstract = {This paper discusses algorithms for labeling sets of points
in the plane, where labels are not restricted to some
finite number of positions. We show that continuously
sliding labels allows more points to be labeled both in
theory and in practice. We define six different models of
labeling, and analyze how much better---more points get a
label---one model can be than another. Maximizing the
number of labeled points is NP-hard, but we show that all
models have a polynomial-time approximation scheme, and all
models have a simple and efficient factor-1/2
approximation algorithm. Finally, we give experimental
results based on the factor-1/2 approximation
algorithm to compare the models in practice.},
update = {98.02 wolff}
}
@TechReport{ksw-pslsl-98t,
author = {Marc van Kreveld and Tycho Strijk and Alexander
Wolff},
title = {Point Set Labeling with Sliding Labels},
institution = UU,
number = {UU-CS-1998-40},
year = 1998,
pdf = {ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-1998/1998-40.pdf}
}
@Article{ksy-lrmsl-01,
author = {Sung Kwon Kim and Chan-Su Shin and Tae-Cheon Yang},
title = {Labeling a rectilinear map with sliding labels},
journal = IJCGA,
year = 2001,
volume = 11,
number = 2,
pages = {167--179},
succeeds = {pzc-ptslr-98, sk-lrmme-99, ksy-lrmsl-99},
url = {http://journals.wspc.com.sg/journals/ijcga/11/1102/S0218195901000432.html},
pdf = {http://journals.wspc.com.sg/journals/ijcga/11/preserved-docs/1102/S0218195901000432.pdf},
abstract = {A rectilinear map consists of a set of mutually
non-intersecting rectilinear (i.e., horizontal or
vertical) line segments, and each segment is allowed
to use a rectangular label of height $B$ and length
the same as the segment. Sliding labels are not
restricted to any finite number of predefined
positions but can slide and be placed at any
position as long as it intersects the segment. This
paper considers three versions of the problem of
labeling a rectilinear map with sliding labels and
presents efficient exact and approximation
algorithms for them.}
}
@TechReport{ksy-lrmsl-99,
author = {Sung Kwon Kim and Chan-Su Shin and Tae-Cheon Yang},
title = {Labeling a rectilinear map with sliding labels},
institution = {Hongkong University of Science and Technology},
year = 1999,
number = {HKUST-TCSC-1999-06},
month = jul,
annote = {non-intersecting axis-parallel line segments are
labeled with sliding labels; label height is
maximized},
url = {http://www.cs.ust.hk/tcsc/RR/index_2.html},
postscript = {http://www.cs.ust.hk/tcsc/RR/1999-06.ps.gz}
}
@InProceedings{kt-alehd-97,
author = {Konstantinos G. Kakoulis and Ioannis G. Tollis},
title = {An Algorithm for Labeling Edges of Hierarchical
Drawings},
booktitle = {Proc. Symp. 5th Internat. Symp. on Graph Drawing (GD'97)},
series = LNCS,
publisher = SV,
volume = 1353,
year = 1997,
pages = {169--180},
postscript = {http://www.utdallas.edu/\~{}tollis/papers/labeling_GD97.ps}
}
@Article{kt-celpp-01,
author = {Konstantinos G. Kakoulis and Ioannis G. Tollis},
title = {On the Complexity of the Edge Label Placement Problem},
journal = CGTA,
year = 2001,
volume = 18,
number = 1,
pages = {1--17},
postscript = { },
succeeds = {kt-elpp-97, w-spnph-00}
}
@InProceedings{kt-elpp-97,
author = {Konstantinos G. Kakoulis and Ioannis G. Tollis},
title = {On the Edge Label Placement Problem},
booktitle = {Proc. Symp. 4th Internat. Symp. on Graph Drawing (GD'96)},
series = LNCS,
publisher = SV,
volume = 1190,
year = 1997,
pages = {241--256},
postscript = {http://www.utdallas.edu/\~{}tollis/papers/labeling_GD96.ps}
}
@InProceedings{kt-mlpp-98,
author = {Konstantinos G. Kakoulis and Ioannis G. Tollis},
title = {On the Multiple Label Placement Problem},
pages = {66--67},
booktitle = {Proc. 10th Canadian Conf. Computational Geometry (CCCG'98)},
year = 1998,
confmonth = {10--12~} # aug,
address = {Montr{\'e}al},
postscript = {http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-kakoulis-multiple.ps.gz}
}
@Article{kt-uaalp-03,
author = {Konstantinos G. Kakoulis and Ioannis G. Tollis},
title = {A Unified Approach to Automatic Label Placement},
journal = IJCGA,
year = 2003,
volume = 13,
number = 1,
pages = {23--59}
}
@InProceedings{kt-ualgf-98,
author = {Konstantinos G. Kakoulis and Ioannis G. Tollis},
title = {A Unified Approach to Labeling Graphical Features},
booktitle = {Proc. 14th Annu. ACM Sympos. Comput. Geom. (SoCG'98)},
year = 1998,
month = jun,
pages = {347--356},
postscript = {http://www.utdallas.edu/\~{}tollis/papers/labeling_CG98.ps},
update = {98.06 strijk}
}
@TechReport{l-anpcc-84,
author = {Zhong Lee},
title = {Automatic Name Placement of {C}anadian Census Map},
institution = {Department of Electrical and Computer Enginering,
Rutgers University, Piscataway, NJ},
year = 1984
}
@MastersThesis{l-aplgd-82,
author = {G.E. Lewis},
title = {Automated Point Labeling for Geographic Data Bases},
school = {Department of Geography, Western Washington
University, Bellingham, Washington},
year = 1982
}
@Misc{l-cs-01,
author = {Gerrit Leeflang},
title = {Cartografie in stroomversnelling},
howpublished = {Newspaper article in \emph{De Telegraaf}},
month = {20~} # jan,
year = 2001,
number = {35113},
pages = {TA21},
url = MAPLABURL # {l-cs-01.jpg},
language = {dutch}
}
@TechReport{l-iafnp-84,
author = {V. Lacroix},
title = {An Improved Area-Feature Name Placement},
institution = {Image Processing Lab., ECSE Dept., Rensselaer
Polytechnic Institute, Troy, NY 12181},
year = 1984,
number = {IPL-TR-064}
}
@InProceedings{lp-insnp-86,
author = {Gail E. Langran and Thomas K. Poiker},
title = {Integration of Name Selection and Name Placement},
booktitle = {Proc. 2nd Internat. Sympos. Spatial Data Handling
(SDH'86)},
year = 1986,
location = {Seattle},
pages = {50--64}
}
@InProceedings{lpclbc-paecq-94,
author = {F. Lecordix and Corinne Plazanet and F. Chiri{\'e} and
J.P. Lagrange and T. Banel and Y. Cras},
title = {Placement Automatique des {\'E}critures d'une Carte
avec une Qualit{\'e} Cartographique},
booktitle = {Proc. EGIS'94},
language = {french},
year = 1994,
pages = {22--32}
}
@TechReport{lps-dolpi-98,
author = {Jia Li and Catharine Plaisant and Ben Shneiderman},
title = {Data Object and Label Placement for Information Abundant Visualizations},
institution = {Department of Computer Science, University of Maryland},
year = 1998,
number = {CS-TR-3901, UMIACS-TR-98-28},
postscript = {ftp://ftp.cs.umd.edu/pub/papers/papers/ncstrl.umcp/CS-TR-3901/CS-TR-3901.ps.Z}
}
@Article{lr-hclpp-06,
author = {Luiz Antonio Nogueira Lorena and Glaydston Mattos
Ribeiro},
title = {Heuristics for cartographic label placement problems},
journal = {Computers and GeoSciences},
year = 2006,
volume = 32,
number = 6,
pages = {739--748},
pdf = {http://www.lac.inpe.br/\~{}lorena/glaydston/map_lab_C&Geo.pdf}
}
@InProceedings{lr-lsap-04,
author = {Luiz Antonio Nogueira Lorena and Glaydston Mattos
Ribeiro},
title = {A Lagrangean/surrogate approach to point-feature
cartographic label placement},
booktitle = {Proc. 20th European Conf. Oper. Res. (EUROXX)},
pages = { },
year = 2004,
month = {4--7~} # jul,
location = {Rhodes}
}
@Article{lsc-pblfp-08,
author = "Martin Luboschik and Heidrun Schumann and Hilko
Cords",
title = "Particle-Based Labeling: Fast Point-Feature Labeling
without Obscuring Other Visual Features",
year = 2008,
journal = "IEEE Trans. Visualization \& Comput. Graphics",
volume = 14,
number = 6,
pages = "1237--1244",
abstract = "In many information visualization techniques, labels
are an essential part to communicate the visualized
data. To preserve the expressiveness of the visual
representation, a placed label should neither
occlude other labels nor visual representatives
(e.g., icons, lines) that communicate crucial
information. Optimal, non-overlapping labeling is an
NP-hard problem. Thus, only a few approaches achieve
a fast non-overlapping labeling in highly
interactive scenarios like information
visualization. These approaches generally target the
point-feature label placement (PFLP) problem,
solving only label-label conflicts. This paper
presents a new, fast, solid and flexible 2D labeling
approach for the PFLP problem that additionally
respects other visual elements and the visual extent
of labeled features. The results (number of placed
labels, processing time) of our particle-based
method compare favorably to those of existing
techniques. Although the esthetic quality of
non-real-time approaches may not be achieved with
our method, it complies with practical demands and
thus supports the interactive exploration of
information spaces. In contrast to the known
adjacent techniques, the flexibility of our
technique enables labeling of dense point clouds by
the use of non-occluding distant labels. Our
approach is independent of the underlying
visualization technique, which enables us to
demonstrate the application of our labeling method
within different information visualization
scenarios. ",
keywords = {data visualisationdata visualization, fast point
feature labeling, flexible 2D labeling, information
visualization, non-occluding distant labels,
particle-based labeling, point-feature label
placement problem, visual features, visual
representation},
url = {http://dx.doi.org/10.1109/TVCG.2008.152},
doi = {10.1109/TVCG.2008.152},
}
@MastersThesis{m-acl-05,
author = {Sebastian M{\"u}ller},
title = {Automatic Chart Labeling},
school = {Institut f{\"u}r Informatik,
Humboldt-Universit{\"a}t Berlin},
year = 2005,
month = oct,
abstract = {Labeling algorithms have been researched for at
least 25 years. So far, almost the entire literature
took a very theoretical perspective. This might be a
reason, why automatic labeling has not yet reached
the level of success it deserves. In my diploma
thesis I have developed several algorithms for
labeling the most typical business charts. Those
include column charts, pie charts, and scatter
charts, as well as their derivatives. Each algorithm
is presented independently accompanied by a thorough
discussion of the previous work which has been done
in the field of automatic labeling algorithms. \par
The column chart labeling problem is divided into
two parts. First, a locally optimal labeling
solution for a single column is searched and second,
through iterative reapplication of the first
algorithm, a possibly optimal order is found in
which columns should be labeled. \par The pie chart
labeling problem is easier to solve and is explained
in the relatively short second part. Excellent
results can be obtained by iteratively reapplying
quadratic optimization techniques. \par The last
part explains the scatter chart labeling problem
which is related to the well understood point
feature labeling problem. The search space is
discretized and several efficient heuristics are
employed to yield an approximate solution. \par All
of the algorithms are fully implemented as part of
think-cell chart, a commercial charting package, and
have shown to produce very satisfactory results. The
column chart labeling algorithms have been published
at an international conference and patents are
pending for several algorithms presented herein.}
}
@Article{m-afnpp-93,
author = {James E. Mower},
title = {Automated Feature and Name Placement on Parallel
Computers},
journal = {Cartography and GIS},
year = 1993,
volume = 20,
number = 2,
pages = {69--82}
}
@TechReport{m-alpss-95,
author = {Sean Marrinan},
title = {Automated Label Placement of Soil Survey Maps},
institution = {Department of Electrical and Computer Enginering,
Rutgers University, Piscataway, NJ},
year = 1995,
number = {CE-125}
}
@Misc{m-bgpvl-05,
author = {Moritz Minzlaff},
title = {{Beschriften gewichteter Punkte mit verschiebbaren
Labeln}},
howpublished = {Studienarbeit, Fakult{\"a}t f{\"u}r Informatik,
Universit{\"a}t Karlsruhe},
month = mar,
year = 2005,
pdf = {http://i11www.ira.uka.de/teaching/theses/files/studienarbeit-minzlaff-05.pdf},
succeeds = {pssuw-lpw-03},
language = {ngerman},
note = {Available at \url{http://i11www.ira.uka.de/teaching/theses/files/studienarbeit-minzlaff-05.pdf}}
}
@InCollection{m-ctcc-80,
author = {Joel L. Morrison},
title = {Computer Technology and Cartographic Change},
booktitle = {The Computer in Contemporary Cartography},
year = 1980,
publisher = {Johns Hopkins University Press},
editor = {D.R.F. Taylor},
ISBN = {0-471-27699-5},
location = {Baltimore, MD}
}
@Article{m-fpflp-07,
author = {Kevin D. Mote},
title = {Fast point-feature label placement for dynamic
visualizations},
journal = {Information Visualization},
year = 2007,
volume = 6,
number = 4,
pages = {249--260},
doi = {10.1057/palgrave.ivs.9500163},
url = {http://dx.doi.org/10.1057/palgrave.ivs.9500163},
pdf = {http://www.palgrave-journals.com/ivs/journal/v6/n4/pdf/9500163a.pdf}
}
@Misc{m-lezac-99,
author = {MapText},
title = {Label-{EZ} for Automated Cartographic Text
Placement---A High-Performance Productivity
Tool for the Mapping Industry},
howpublished = {\url{http://www.maptext.com}},
year = 1999,
url = {http://www.maptext.com}
}
@InProceedings{m-nppfc-86,
author = {James E. Mower},
title = {Name Placement of Point Features Through Constraint
Propagation},
booktitle = {Proc. 2nd Internat. Sympos. on Spatial Data
Handling (SDH'86)},
year = 1986,
pages = {65--73}
}
@MastersThesis{m-pak-94,
author = {J.M. Marrot},
title = {Positionnement Automatique des Kilom{\'e}trages},
language = {french},
school = {DESS},
year = 1994
}
@Article{m-pcnpd-94,
author = {William Mills},
title = {Practical Considerations in Name Placement: A
Defence of {Pinhas Yoeli}},
journal = {Cartographica},
year = 1994,
volume = 31,
number = 4,
pages = {58--62},
succeeds = {wb-rrpfn-91}
}
@PhdThesis{m-sieha-89,
author = {James E. Mower},
title = {The Selection, Implementation, and Evaluation of
Heuristics for Automated Name Placement},
school = {The State University of New York at Buffalo},
year = 1989
}
@Misc{m-tmips-99,
author = {MicroImages},
title = {TNTmips---the Map and Image Processing System},
howpublished = {\url{http://tnt.microimages.com/product/tntmips.htm}},
year = 1999,
url = {http://tnt.microimages.com/product/tntmips.htm}
}
@Article{mbhrr-shudg-95,
author = {Madhav V. Marathe and Heinz Breu and Harry B. {Hunt
III} and S.S. Ravi and Daniel J. Rosenkrantz},
title = {Simple Heuristics for Unit Disk Graphs},
journal = {Networks},
volume = 25,
year = 1995,
pages = {59--68},
update = {97.03 kreveld}
}
@InProceedings{md-daieu-06,
author = {Stefan Maass and J{\"u}rgen D{\"o}llner},
title = {Dynamic Annotation of Interactive Environments using
Object-Integrated Billboards},
booktitle = {Proc. 14th Internat. Conf. in Central Europe on
Computer Graphics, Visualization and Computer Vision
(WSCG'06)},
pages = {327--334},
confmonth = jan,
year = 2006,
editor = {Joaquim Jorge and Vaclav Skala},
address = {Plzen, Czech Republic},
keywords = {Annotation, labeling, 3D geo-virtual environments},
pdf = {http://wscg.zcu.cz/wscg2006/Papers_2006/Full/A79-full.pdf}
}
@InProceedings{md-ellfi-07,
author = {Stefan Maass and J{\"u}rgen D{\"o}llner},
title = {Embedded Labels for Line Features in Interactive
{3D} Virtual Environments},
booktitle = {Proc. 5th Internat. ACM Conf. Computer Graphics,
Virtual Reality, Visualization and Interaction in
Africa (AFRIGRAPH'07)},
pages = {53--59},
confmonth = oct,
year = 2007,
keywords = {Labeling, annotation, interactive virtual 3D
environments},
issn = {978-1-59593-906-7},
doi = {http://doi.acm.org/10.1145/1294685.1294695},
}
@InProceedings{md-evmda-08,
author = {Stefan Maass and J{\"u}rgen D{\"o}llner},
title = {Efficient View Management for Dynamic Annotation
Placement in Virtual Landscapes},
booktitle = {Proc. 6th Intnat. Sympos. Smart Graphics (SG'06)},
series = LNCS,
volume = 4073,
pages = {1--12},
confmonth = jul,
year = 2006,
editor = {Andreas Butz and Brian Fischer and Antonio
Kr{\"u}ger and Patrick Oliver},
publisher = SV,
location = {Vancouver, Canada},
keywords = {Annotation, labeling, view management, 3D
geo-virtual environments}
}
@InProceedings{me-luafa-03,
author = {D. Morgenstern and M. Ellsiepen},
title = {Labelling Urban Areas - Formalisation and
Automation},
booktitle = {Proc. 23rd Internat. Cartographic Conf. (ICC'03)},
pages = {277--286},
year = 2003,
address = {Durban, South Africa}
}
@InProceedings{mhr-gbaig-92,
author = {Madhav V. Marathe and Harry B. {Hunt III} and
S.S. Ravi},
title = {Geometry Based Approximations for Intersection
Graphs},
booktitle = {Proc. 4th Canad. Conf. on Computational Geometry},
year = 1992,
pages = {244--249}
}
@InProceedings{mjd-dcoic-07,
author = {Stefan Maass and Markus Jobst and J{\"u}rgen
D{\"o}llner},
title = {Depth Cue of Occlusion Information as Criterion for
the Quality of Annotation Placement in Perspective
Views},
booktitle = {The European Information Society -- Leading the Way
with Geo-Information},
series = {Lecture Notes in Geoinformation and Cartography},
pages = {473--486},
confmonth = aug,
year = 2007,
editor = {Sara Irina Fabrikant and Monica Wachowicz},
publisher = SV,
keywords = {Annotation, labeling, depth-cues, 3D geo-virtual
environments},
issn = {1863-2246},
}
@InProceedings{mjd-udca3-07,
author = {Stefan Maass and Markus Jobst and J{\"u}rgen
D{\"o}llner},
title = {Use of Depth Cues for the Annotation of {3D}
Geo-Virtual Environments},
booktitle = {Proc. 23rd Internat. Cartographic Conf. (ICC'07)},
keywords = {Annotation, labeling, depth-cues, 3D geo-virtual
environments},
confmonth = aug,
year = 2007,
address = {Moscow, Russia}
}
@TechReport{ms-ccclp-91,
author = {Joe Marks and Stuart Shieber},
title = {The Computational Complexity of Cartographic Label
Placement},
institution = {Harvard CS},
year = 1991,
number = {TR-05-91},
pdf = {http://www.eecs.harvard.edu/\{}~shieber/Biblio/Papers/label.pdf},
update = {98.01 wolff}
}
@InProceedings{ms-saccl-05,
author = {Sebastian M{\"u}ller and Arno Sch{\"o}dl},
title = {A Smart Algorithm for Column Chart Labeling},
booktitle = {Proc. Smart Graphics (SG'05)},
pages = {127--137},
year = 2005,
editor = {Andreas Butz and Brian Fisher and Antonio Krüger and
Patrick Olivier},
volume = 3638,
series = LNCS,
publisher = SV,
location = {Kloster Frauenw{\"o}rth, Germany},
url = {http://dx.doi.org/10.1007/11536482_11},
doi = {10.1007/11536482_11},
abstract = {This paper presents a smart algorithm for labeling
column charts and their derivatives. To efficiently
solve the problem, we separate it into two
sub-problems. We first present a geometric algorithm
to solve the problem of finding a good labeling for
the labels of a single column, given that some other
columns have already been labeled. We then present a
strategy for finding a good order in which columns
should be labeled, which repeatedly uses the first
algorithm for some limited look-ahead. The presented
algorithm is being used in a commercial product to
label charts, and has shown in practice to produce
satisfactory results.}
}
@InProceedings{mt-fnpsg-99,
author = {Vladimir Miroshnikov and Evgueni Tchepine},
title = {A Framework for Name Placement Solving in {GIS}},
booktitle = {Proc. Workshop on Computer Science and
Information Technologies (CSIT)},
year = 1999,
pages = {187--190},
url = {http://msu.jurinfor.ru/CSIT99/MiroshnikovC99.htm},
pdf = {http://msu.jurinfor.ru/CSIT99/Ru-079-f.pdf}
}
@Article{n-hmlps-87,
author = {E. Noma},
title = {Heuristic Method for Label Placement in
Scatterplots},
journal = {Psychometrika},
year = 1987,
volume = 52,
number = 3,
pages = {463--468}
}
@InCollection{n-mlagd-01,
author = {Gabriele Neyer},
title = {Map Labeling with Application to Graph Drawing},
booktitle = {Drawing Graphs: Methods and Models},
series = LNCS,
volume = 2025,
publisher = SV,
year = 2001,
editor = {Dorothea Wagner and Michael Kaufmann},
pages = {247--273},
url = {http://link.springer.de/link/service/series/0558/bibs/2025/20250247.htm},
pdf = {http://link.springer.de/link/service/series/0558/papers/2025/20250247.pdf}
}
@TechReport{n-obdam-85,
author = {J. Nastelin},
title = {Optimization of Baseline Determination for Area Map
Annotation},
institution = {Image Processing Lab., ECSE Dept., Rensselaer
Polytechnic Institue, Troy, NY 12181},
year = 1985,
number = {IPL-TR-078}
}
@InProceedings{ne-uhml-03,
author = {Hugo A. D. do Nascimento and Peter Eades},
title = {User hints for map labelling},
booktitle = {Proc. 26th Australasian Computer Science Conf.},
pages = {339--347},
year = 2003,
series = {ACM Internat. Conf. Proceeding Series},
location = {Adelaide},
url = {http://portal.acm.org/citation.cfm?id=783145&dl=ACM&coll=portal&CFID=21928415&CFTOKEN=20741064},
pdf = {http://portal.acm.org/ft_gateway.cfm?id=783145&type=pdf&coll=portal&dl=ACM&CFID=21928415&CFTOKEN=20741064},
abstract = {The Map Labelling Problem appears in several
applications, mainly in Cartography. Although much
research on this problem has been done, it is
interesting to note that map-labelling processes in
commercial fields are very often executed manually
or with little support of automatic tools. In
general, practical map-labelling problems involve
human subjective domain knowledge about label
placement that is not entirely covered by the
existing scientific approaches. In the present
paper, we describe an interactive framework for
minimising this technological gap. The framework
allows users to interact with a labelling process by
giving hints, which represent domain knowledge or
adjustments that help an optimisation method to
produce good labelling results. A map labelling
system based on the framework has been implemented
and an initial evaluation shows that it is
promising.}
}
@Article{ne-uhml-08,
author = {Hugo A. D. do Nascimento and Peter Eades},
title = {User Hints for Map Labeling},
journal = {J. Visual Languages \& Comput.},
year = 2008,
volume = 19,
number = 1,
pages = {39--74},
doi = {10.1016/j.jvlc.2006.03.004},
url = {http://dx.doi.org/10.1016/j.jvlc.2006.03.004}
}
@InProceedings{nntw-lprvs-01,
author = {{Shin-ichi} Nakano and Takao Nishizeki and Takeshi
Tokuyama and Shuhei Watanabe},
title = {Labeling Points with Rectangles of Various Shapes},
booktitle = {Proc. Symp. 8th Internat. Symp. on Graph Drawing (GD'00)},
pages = {91--102},
year = 2001,
series = LNCS,
volume = 1984,
publisher = SV
}
@InProceedings{nw-ld-00,
author = {Gabriele Neyer and Frank Wagner},
title = {Labeling Downtown},
booktitle = {Proc. Italian Conf. on Algorithms and
Complexity (CIAC'00)},
year = 2000,
series = LNCS,
volume = 1767,
publisher = SV,
pages = {113--125},
url = {http://link.springer.de/link/service/series/0558/bibs/1767/17670113.htm},
pdf = {http://link.springer.de/link/service/series/0558/papers/1767/17670113.pdf},
abstract = {American cities, especially their central regions
usually have a very regular street pattern: We are
given a rectangular grid of streets, each street has
to be labeled with a name running along its street,
such that no two labels overlap. For this restricted
but yet realistic case an efficient algorithmic
solution for the generally hard labeling problem
gets in reach.
\par
The main contribution of this paper is an algorithm
that guarantees to solve every solvable instance. In
our experiments the running time is polynomial
without a single exception. On the other hand the
problem was recently shown to be NP-hard.
\par
Finally, we present efficient algorithms for three
special cases including the case of having no labels
that are more than half the length of their street.},
succeeds = {nw-ld-99}
}
@TechReport{nw-ld-99,
author = {Gabriele Neyer and Frank Wagner},
title = {Labeling Downtown},
institution = {Department of Computer Science, ETH Zurich},
year = 1999,
number = {TR-324},
month = may,
postscript = {http://webdoc.gwdg.de/ebook/ah/2000/ethz/tech-reports/3xx/324.ps},
cites = {eis-ctmfp-76, gg-dtdfs-95, gj-cigtn-79, nh-mlagl-00,
w-rpop-96, ZZZ},
abstract = {American cities, especially their central regions
usually have a very regular street pattern: We are
given a rectangular grid of streets, each street has
to be labeled with a name running along its street,
such that no two labels overlap. For this restricted
but yet realistic case an efficient algorithmic
solution for the generally hard labeling problem
gets in reach.
\par
The main contribution of this paper is an algorithm
that guarantees to solve every solvable instance. So
far we are not able to provide a runtime analysis
that guarantees efficiency, but the empirical
behavior is polynomial without a single
exception. The complexity status of the problem is
open, we show that a slight generalization, namely
the labeling of a cylinder shaped downtown, is
NP-hard.
\par
Finally, we present efficient algorithms for three
special cases including the case of having no labels
that are more than half the length of their street.},
precedes = {nw-ld-00}
}
@TechReport{om-cii-07,
author = {Kristien Ooms and Philippe De Maeyer},
title = {Cartografische implementatie van de {ITGI}},
institution = {Vakgroep Geografie, Universiteit Gent},
year = 2007,
pdf = {http://cartogis.ugent.be/kooms/toponymie_final.pdf}
}
@Article{om-mbdt-08,
author = {Kristien Ooms and Philippe de Maeyer},
title = {Mogelijkheden en beperkingen van dynamische
tekstplaatsing},
journal = {Geo-Info},
year = 2008,
volume = 5,
number = 5,
pdf = {http://www.geo-info.nl/site/Components/FileCP/Download.aspx?id=4a405b0c-2629-4688-8a8f-f680a1ddcb78}
}
@InProceedings{op-ifla-98,
author = {Lettie Ozuna and Sonny Parafina},
title = {Improving Feature Labeling in {ArcView}},
booktitle = {Proc. GIS/LIS},
year = 1998,
note = {To appear},
url = {http://www.gislis.org/abstracts/ozuna.html}
}
@TechReport{p-anpss-94,
author = {Mehul S. Pandya},
title = {Automated Name-Placement of Soil Survey Maps},
institution = {Department of Electrical and Computer Enginering,
Rutgers University, Piscataway, NJ},
year = 1994,
number = {CE-103}
}
@MastersThesis{p-npvp-93,
author = {Bettina Preis},
title = {{E}in {NP}-vollst{\"a}ndiges {P}lazierungsproblem},
school = {Fachbereich Informatik, Universit{\"a}t des
Saarlandes, Saarbr{\"u}cken},
year = 1993,
month = feb,
language = {german},
update = {00.07 wolff}
}
@MastersThesis{p-smlpm-98,
author = {Mike Preu{\ss}},
title = {Solving Map Labeling Problems by Means of Evolution
Strategies},
school = {Fachbereich Informatik, Universit{\"a}t Dortmund},
year = 1998,
month = feb,
postscript = MAPLABURL # {p-smlpm-98.ps.zip}
}
@MastersThesis{p-tdek-96,
author = {Ingo Petzold},
title = {{T}extplazierung in dynamisch erzeugten {K}arten},
school = {Institut f{\"u}r Informatik III, Universit{\"a}t Bonn},
year = 1996,
month = dec,
url = {http://www.ikg.uni-bonn.de/Publikationen/Diplomarbeiten/ingo_petzold.zip},
language = {german}
}
@InProceedings{pbhhor-aces-85,
author = {C. Pfefferkorn and D. Burr and D. Harrison and
B. Heckman and C. Oresky and J. Rothermel},
title = {{ACES}: A Cartographic Expert System},
booktitle = {Proc. Auto-Carto 7},
year = 1985,
pages = {399--407},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-7/pdf/aces-a-cartographic-expert-system.pdf}
}
@InCollection{pf-facat-96,
author = {Itzhak Pinto and Herbert Freeman},
title = {The Feedback Approach to Cartographic Areal Text
Placement},
booktitle = {Advances in Structural and Syntactical Pattern
Recognition},
publisher = SV # {, New York},
year = 1996,
editor = {P. Perner and P. Wang and A. Rosenfeld},
pages = {341--350},
update = {98.01 wolff}
}
@InProceedings{pgp-fsmld-03,
author = {Ingo Petzold and Gerhard Gr{\"o}ger and Lutz
Pl{\"u}mer},
title = {Fast Screen Map Labeling---Data-Structures and
Algorithms},
booktitle = {Proc. 23rd Internat. Cartographic Conf. (ICC'03)},
address = {Durban, South Africa},
pages = {288--298},
year = 2003,
pdf = {http://www.geo.unizh.ch/\~{}petzold/publications/petzold_icc03.pdf},
succeeds = {pph-lpdgs-99},
abstract = {This paper presents a new and very efficient
technique for automatic labeling of dynamically
generated screen maps. Such screen maps are
frequently created in the course of the interactive
navigation in a geographic information system. Since
screen maps have to support the functions zooming
and scrolling, the label placement must be achieved
very fast. Therefore we developed a concept which
separates the labeling process into two
phases. Calculations are shifted in a socalled
preprocessing-phase as far as possible. Thus, the
number of time consuming operations in the time
critical interaction-phase is reduced and the
operation zooming and scrolling can be realized very
fast. Our concept supports labeling of point objects
as well as labeling of line and area objects. \par
The separation in the two phases is achieved by a
new reactive data-structure which is called reactive
conflict graph. In the preprocessing phase, it
stores information about all potential
conflicts. During the interaction-phase this
structure is optimally exploited and leads to a
labeling in an efficient and a cartographic adequate
way.}
}
@InProceedings{pgp-mcsml-04,
author = {Ingo Petzold and Gerhard Gr{\"o}ger and Lutz
Pl{\"u}mer},
title = {Modeling of Conflicts for Screen Map Labeling},
booktitle = {Proc. 20th ISPRS Congress},
year = 2004,
volume = {34, Part B4},
series = {Internat. Archives of the Photogrammetry, Remote
Sensing and Spatial Information Sciences},
address = {Istanbul},
pdf = {http://www.isprs.org/istanbul2004/comm4/papers/347.pdf}
}
@Article{pp-pbdeb-97,
author = {Ingo Petzold and Lutz Pl{\"u}mer},
title = {{P}lazierung der {B}eschriftung in dynamisch erzeugten
{B}ildschirmkarten},
journal = {Nachrichten aus dem Karten- und Vermessungswesen},
series = {I},
year = 1997,
number = 117,
pages = {95--113},
publisher = {Verlag des Instituts f{\"u}r Angewandte Geod{\"a}sie},
address = {Frankfurt am Main},
language = {german},
url = {http://www.ikg.uni-bonn.de/Publikationen/aga97.zip}
}
@InProceedings{pph-lpdgs-99,
author = {Ingo Petzold and Lutz Pl{\"u}mer and Markus Heber},
title = {Label Placement for Dynamically Generated Screen
Maps},
booktitle = {Proc. 19th Internat. Cartographic Conf. (ICC'99)},
address = {Ottawa, Canada},
year = 1999,
pages = {893--903},
vol = {1},
url = {http://www.ikg.uni-bonn.de/uploads/tx_ikgpublication/ica99-paper_pdf-ps.zip}
}
@InProceedings{ps-abnpm-99,
author = {Lilian Pun-Cheng and Geoffrey Y.K. Shea},
title = {Automatic Bilingual Name Placement of 1:1000 Map
Sheets of Hong Kong},
booktitle = {Proc. 19th Internat. Cartographic Conf. (ICC'99)},
address = {Ottawa, Canada},
year = 1999,
pages = {925--930},
vol = {1}
}
@InProceedings{ps-azpsl-05,
author = {Sheung-Hung Poon and Chan-Su Shin},
title = {Adaptive Zooming in Point Set Labeling},
booktitle = {Proc. 15th Internat. Sympos. Fundam. Comput. Theory
(FCT'05)},
editor = {M. Li{\'s}kiewicz and R. Reischuk},
year = 2005,
pages = {233--244},
series = LNCS,
volume = 3623,
publisher = SV,
url = {http://dx.doi.org/10.1007/11537311_21},
doi = {10.1007/11537311_21}
}
@Article{pssuw-lpw-03,
author = {Sheung-Hung Poon and Chan-Su Shin and Tycho Strijk
and Takeaki Uno and Alexander Wolff},
title = {Labeling Points with Weights},
journal = {Algorithmica},
year = 2003,
volume = 38,
number = 2,
pages = {341--362},
pdf = AWPUBURL # {pssuw-lpw-03.pdf},
url = {http://dx.doi.org/10.1007/s00453-003-1063-0},
doi = {10.1007/s00453-003-1063-0},
cites = {af-aesam-84, aks-lpmis-98, bd-mpatm-00, c-cgitf-99,
cms-esapf-95, ejs-ptasg-01, fw-ppalm-91,
gimprw-lsl-01, gj-cigtn-79, h-aanpa-82, hm-ascpp-85,
htc-eafmw-92, i-mlp-99, m-ctcc-80, pssw-lpw-01i,
sk-pepls-02, ksw-plsl-99, ws-mlb-96, z-sl01i-90,
ZZZ},
succeeds = {pssw-lpw-01i},
abstract = {Annotating maps, graphs, and diagrams with pieces of
text is an important step in information
visualization that is usually referred to as label
placement. We define nine label-placement models for
labeling points with axis-parallel rectangles given
a weight for each point. There are two groups;
fixed-position models and slider models. We aim to
maximize the weight sum of those points that receive
a label. \par We first compare our models by giving
bounds for the ratios between the weights of
maximum-weight labelings in different models. Then
we present algorithms for labeling $n$ points with
unit-height rectangles. We show how an $O(n\log
n)$-time factor-2 approximation algorithm and a PTAS
for fixed-position models can be extended to handle
the weighted case. Our main contribution is the
first algorithm for weighted sliding labels. Its
approximation factor is $(2+\varepsilon)$, it runs
in $O(n^2/\varepsilon)$ time and uses
$O(n/\varepsilon)$ space. We show that other than
for fixed-position models even the projection to one
dimension remains NP-hard. \par For slider models we
also investigate some special cases, namely (a)~the
number of different point weights is bounded,
(b)~all labels are unit squares, and (c)~the ratio
between maximum and minimum label height is
bounded.}
}
@InProceedings{pssw-lpw-01,
author = {Sheung-Hung Poon and Chan-Su Shin and Tycho Strijk
and Alexander Wolff},
title = {Labeling Points with Weights},
booktitle = {Proc. 17th European Workshop Comput.
Geom. (CG'01)},
year = 2001,
pages = {97--100},
location = {Berlin},
month = {26--28~} # mar,
pdf = AWPUBURL # {pssw-lpw-01.pdf},
cites = {bd-itmrt-00, c-accgc-96, ejs-ptasg-01, htc-eafmw-92,
i-mlp-99, sk-pepls-99, ksw-plsl-99, ZZZ},
abstract = {Annotating maps, graphs, and diagrams with pieces of
text is an important step in information
visualization that is usually refered to as label
placement. We define nine label-placement models for
labeling points with axis-parallel rectangles given
a weight for each point. There are two groups;
fixed-position models and slider models. We aim to
maximize the weight sum of those points that receive
a label. We first compare our models by giving
bounds for the ratios between the weights of
maximum-weight labelings in different models. Then
we present algorithms for unit-height labels. We
give an $O(n\log n)$-time factor-2 approximation
algorithm for fixed-position models and the first
algorithm for labeling weighted points with sliding
labels. Its approximation factor is
$(2+\varepsilon)$ and its runtime in
$O(n^2/\varepsilon)$ for any $\varepsilon>0$.}
}
@InProceedings{pssw-lpw-01i,
author = {Sheung-Hung Poon and Chan-Su Shin and Tycho Strijk
and Alexander Wolff},
title = {Labeling Points with Weights},
booktitle = {Proc. 12th Annu. Internat. Sympos.
Algorithms Comput. (ISAAC'01)},
editor = {Peter Eades and Tadao Takaoka},
series = LNCS,
publisher = SV,
volume = 2223,
year = 2001,
pages = {610--622},
location = {Christchurch},
month = {19--21~} # dec,
url = {http://link.springer.de/link/service/series/0558/bibs/2223/22230610.htm},
pdf = AWPUBURL # {pssw-lpw-01i.pdf},
cites = {aks-lpmis-98, bd-mpatm-00, c-cgitf-99, cms-esapf-95,
ejs-ptasg-01, fw-ppalm-91, htc-eafmw-92, i-mlp-99,
m-ctcc-80, pssw-lpw-01t, sk-pepls-99, ksw-plsl-99,
ZZZ},
succedes = {pssw-lpw-01},
precedes = {pssuw-lpw-03},
abstract = {Annotating maps, graphs, and diagrams with pieces of
text is an important step in information
visualization that is usually referred to as label
placement. We define nine label-placement models for
labeling points with axis-parallel rectangles given
a weight for each point. There are two groups;
fixed-position models and slider models. We aim to
maximize the weight sum of those points that receive
a label. We first compare our models by giving
bounds for the ratios between the weights of
maximum-weight labelings in different models. Then
we present algorithms for labeling $n$ points with
unit-height rectangles. We show how an $O(n\log
n)$-time factor-2 approximation algorithm and a PTAS
for fixed-position models can be extended to handle
the weighted case. Our main contribution is the
first algorithm for weighted sliding labels. Its
approximation factor is $(2+\varepsilon)$, it runs
in $O(n^2/\varepsilon)$ time and uses
$O(n/\varepsilon)$ space. We also investigate some
special cases.}
}
@TechReport{pssw-lpw-01t,
author = {Sheung-Hung Poon and Chan-Su Shin and Tycho Strijk
and Alexander Wolff},
title = {Labeling Points with Weights},
institution = UG,
year = 2001,
number = {7/2001},
month = may,
msc = {65D18, 90B35, 68W25, 68R05},
keywords = {computational geometry, GIS, label placement,
sliding labels, combinatorial optimization, job
scheduling, throughput maximization, maximum
weight independent set},
url = {http://www.math-inf.uni-greifswald.de/preprints/shadow/wolff01_7.rdf.html},
pdf = {http://www.math-inf.uni-greifswald.de/pub/full/prep/2001/wolff01_7.pdf},
abstract = {Annotating maps, graphs, and diagrams with pieces of
text is an important step in information
visualization that is usually referred to as label
placement. We define nine label-placement models for
labeling points with axis-parallel rectangles given
a weight for each point. There are two groups;
fixed-position models and slider models. We aim to
maximize the weight sum of those points that receive
a label.
\par
We first compare our models by giving bounds for the
ratios between the weights of maximum-weight
labelings in different models. Then we present
algorithms for labeling $n$ points with unit-height
rectangles. We show how an $O(n\log n)$-time
factor-2 approximation algorithm and a PTAS for
fixed-position models can be extended to handle the
weighted case. Our main contribution is the first
algorithm for weighted sliding labels. Its
approximation factor is $(2+\varepsilon)$, it runs
in $O(n^2/\varepsilon)$ time and uses
$O(n/\varepsilon)$ space.
\par
Next we describe a factor-2 approximation for the
case that the number of different weights is bounded
and a PTAS for labeling points with sliding
unit-square labels. Finally, for instances with a
constant ratio $\beta$ of maximum to minimum label
height we give algorithms with approximation factors
of $3 \lceil \log_2 \beta \rceil$ and
$(3+\varepsilon) \lceil \log_2 \beta \rceil$
assuming fixed-position and slider models,
respectively.},
cites = {af-aesam-84, aks-lpmis-98, bd-mpatm-00, c-cgitf-99,
cms-esapf-95, ejs-ptasg-01, h-aanpa-82, hm-ascpp-85,
htc-eafmw-92, i-mlp-99, sk-pepls-99, ksw-plsl-99,
ws-mlb-96, ZZZ},
succeeds = {pssw-lpw-01}
}
@InProceedings{pzc-ptslr-97,
author = {Chung Keung Poon and Binhai Zhu and Francis Chin},
title = {A Polynomial Time Solution for Labeling a
Rectilinear Map},
booktitle = {Proc. 13th Annu. ACM Sympos. Comput. Geom. (SoCG'97)},
year = 1997,
pages = {451--453},
update = {97.07 efrat}
}
@Article{pzc-ptslr-98,
author = {Chung Keung Poon and Binhai Zhu and Francis Chin},
title = {A Polynomial Time Solution for Labeling a
Rectilinear Map},
pages = {201--207},
journal = IPL,
year = 1998,
volume = 65,
number = 4,
cites = {\cite{CACM::DoerschlerF1992}
\cite{SICOMP::EvenIS1976} \cite{IPL::Wagner1994}},
update = {98.04 strijk}
}
@InProceedings{qwxz-na2lp-00,
author = {Zhongping Qin and Alexander Wolff and Yinfeng Xu and
Binhai Zhu},
title = {New Algorithms for Two-Label Point Labeling},
booktitle = {Proc. 8th Annu. European Sympos. Algorithms (ESA'00)},
editor = {Mike Paterson},
year = 2000,
volume = 1879,
pages = {368--379},
series = LNCS,
location = {Saarbr{\"u}cken},
confmonth = {5--8~} # sep,
publisher = SV,
succeeds = {kt-mlpp-98, zp-eaaml-99, zq-naaml-02, qwxz-na2lp-00t},
precedes = {wtx-blb2c-00},
cites = {af-aesam-84, a-vdsfg-91, c-accgc-96, cms-esapf-95,
dlss-sdakp-95, dmmmz-mlg-97, dmm-pslsp-00,
df-esdmn-89, eis-ctmfp-76, f-agpsp-92, fw-ppalm-91,
fw-eskml-93, h-aanpa-82, kt-mlpp-98, kr-pcr-92,
pzc-ptslr-98, sw-lpc-99, ksw-plsl-99, ww-pmla-97,
zp-eaaml-99, zq-naaml-02, ZZZ},
abstract = {Given a label shape $L$ and a set of $n$ points in
the plane, the 2-label point-labeling problem
consists of placing $2n$ non-intersecting translated
copies of $L$ of maximum size such that each point
touches two unique copies---its labels. In this
paper we give new and simple approximation
algorithms for $L$ an axis-parallel square or a
circle. For squares we improve the best previously
known approximation factor from $1/3$ to
$1/2$. For circles the improvement from
$1/2$ to $\approx 0.513$ is less
significant, but the fact that $1/2$ is not
best possible is interesting in its own right. For
the decision version of the latter problem we have
an NP-hardness proof that also shows that it is
NP-hard to approximate the label size beyond a
factor of $\approx 0.732$. As their predecessors,
our algorithms take $O(n \log n)$ time and $O(n)$
space.},
pdf = AWPUBURL # {qwxz-na2lp-00.pdf}
}
@TechReport{qwxz-na2lp-00t,
author = {Zhongping Qin and Alexander Wolff and Yinfeng Xu and
Binhai Zhu},
title = {New Algorithms for Two-Label Point Labeling},
institution = {Hongkong University of Science and Technology},
year = 2000,
number = {HKUST-TCSC-2000-06},
month = jun,
abstract = {Given a label shape $L$ and a set of $n$ points in
the plane, the two-label point-labeling problem
consists of placing $2n$ non-intersecting translated
copies of $L$ of maximum size such that each point
touches two unique copies---its labels.
\par
In this paper we give new and simple approximation
algorithms for $L$ an axis-parallel square or a
circle. For squares we improve the best previously
known approximation factor from $1/3$ to
$1/2$. For circles the improvement from
$1/2$ to roughly 0.5125 is less significant,
but the fact that $1/2$ is not best possible
is interesting in its own right. For the decision
version of the latter problem we have an NP-hardness
proof that also shows that it is NP-hard to
approximate the label size beyond a factor of
$\approx 0.7321$. We keep the $O(n \log n)$ time and
$O(n)$ space bounds of the previous algorithms.
\par
The algorithm we propose for the two-square labeling
problem actually solves a different problem. It
labels points with rectangles of height-width ratio
2 of maximum size in one of four positions. It is
the first point-labeling algorithm that combines the
following properties. It allows more than two label
positions \emph{and} solves the size maximization
problem optimally in polynomial time. This algorithm
also improves the approximation factor of the only
known algorithm for Knuth and Raghunathan's Metafont
labeling problem from $1/3$ to
$1/2$.},
url = {http://www.cs.ust.hk/tcsc/RR/index_3.html},
postscript = {http://www.cs.ust.hk/tcsc/RR/2000-06.ps.gz}
}
@InProceedings{qz-f2alp-02,
author = {Zhongping Qin and Binhai Zhu},
title = {A factor-2 approximation for labeling points with
maximum sliding labels},
booktitle = {Proc. 8th Scandinavian Workshop on Algorithm Theory
(SWAT'02)},
pages = {100--109},
year = 2002,
editor = {Martti Penttonen and Erik Meineche Schmidt},
volume = 2368,
series = LNCS,
location = {Turku},
month = {3--5~} # jul,
publisher = SV,
url = {http://link.springer.de/link/service/series/0558/bibs/2368/23680100.htm},
pdf = {http://link.springer.de/link/service/series/0558/papers/2368/23680100.pdf},
abstract = {In this paper we present a simple approximation
algorithm for the following NP-hard map labeling
problem: Given a set $S$ of $n$ distinct sites in
the plane, one needs to place at each site an
axis-parallel sliding square of maximum possible
size (i.e., a site can be anywhere on the boundary
of its labeling square) such that no two squares
overlap and all the squares have the same size. By
exploiting the geometric properties of the problem,
we reduce a potential 4SAT problem to a 2SAT
problem. We obtain a factor-2 approximation which
runs in $O(n^2 \log n)$ time using discrete
labels. This greatly improves the previous factor of
4.}
}
@InProceedings{r-alclb-87,
author = {Jan W. van Roessel},
title = {An Algorithm for Locating Candidate Labeling Boxes
within a Polygon},
booktitle = {Proc. Auto-Carto 8},
year = 1987,
pages = {689--700},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-8/pdf/an-algorithm-for-locating-candidate-labeling-boxes-within-a-polygon.pdf}
}
@Article{r-alclb-89,
author = {Jan W. van Roessel},
title = {An Algorithm for Locating Candidate Labeling Boxes
within a Polygon},
journal = {The American Cartographer},
year = 1989,
volume = 16,
number = 3,
pages = {201-209},
update = {98.01 wolff}
}
@InProceedings{r-eapfl-99,
author = {G\"{u}nther Raidl},
title = {An Evolutionary Approach to Point-Feature Label
Placement},
booktitle = {Proc. Genetic and Evolutionary
Computation Conf. (GECCO'99)},
year = 1999,
editor = {W. Banzhaf and J. Daida and A.E. Eiben and
M.H. Garzon and V. Honavar and M. Jakiela and
R.E. Smith},
confmonth = jul,
publisher = {Morgan Kaufmann},
vol = 1,
pages = 807
}
@InProceedings{r-galpf-98,
author = {G{\"u}nther Raidl},
title = {A Genetic Algorithm for Labeling Point Features},
booktitle = {Proc. Internat. Conf. Imaging Science,
Systems, and Technology (CISST'98)},
pages = {189--196},
year = 1998,
address = {Las Vegas, NV},
confmonth = jul
}
@MastersThesis{r-olgas-98,
author = {Wolfgang Rumplmaier},
title = {{O}ptimierung von {L}abelanordnungen mit {G}enetischen
{A}lgorithmen und {S}imulated {A}nnealing},
school = {Institute of Computer Graphics, Vienna University
of Technology},
year = 1998,
month = apr,
language = {german}
}
@PhdThesis{r-pecc-02,
author = "Pedro Reyes",
title = {Problemas de Etiquetado: Complejidad Computacional},
school = "Departamento de Matem{\'a}tica Aplicada I,
Universidad de Sevilla",
year = 2002,
}
@InProceedings{rg-afaula-04,
title = {A Fast Algorithm for Updating a Labeling to Avoid a
Moving Point},
author = {Farshad Rostamabadi and Mohammad Ghodsi},
booktitle = {Proc. 16th Canadian Conf. on Computational
Geometry (CCCG'04)},
site = {Montr\'{e}al},
year = 2004,
pages = {204--208},
pdf = {http://www.cs.concordia.ca/cccg/papers/19.pdf}
}
@InProceedings{rg-ealu2-05,
author = {Farshad Rostamabadi and Mohammad Ghodsi},
title = {An Efficient Algorithm for Label Updating in {2PM}
Model to Avoid a Moving Object},
booktitle = {Proc. 21st European Workshop Comput.
Geom. (EWCG'05)},
pages = {131--134},
year = 2005,
location = {Eindhoven},
month = {9--11~} # mar,
pdf = {http://www.win.tue.nl/EWCG2005/Proceedings/34.pdf},
succeeds = {rg-afaula-04}
}
@InProceedings{rg-uhkpm-03,
author = {Farshad Rostamabadi and Mohammad Ghodsi},
title = {Unit Height $k$-Position Map Labeling},
booktitle = {Proc. 19th European Workshop Comput.
Geom. (EWCG'03)},
pages = { },
year = 2003,
location = {Bonn},
month = mar,
postscript = {http://sina.sharif.edu/~ghodsi/papers/rg-ewcg2003.ps.gz}
}
@InProceedings{rgdn-oaspl-02,
author = {Sasanka Roy and Partha P. Goswami and Sandip Das and
Subhas C. Nandy},
title = {Optimal Algorithm for a Special Point-Labeling
Problem},
booktitle = {Proc. 8th Scandinavian Workshop on Algorithm Theory
(SWAT'02)},
pages = {110--120},
year = 2002,
editor = {M. Penttonen and E. Meineche Schmidt},
volume = 2368,
series = LNCS,
location = {Turku},
confmonth = {3--5~} # jul,
publisher = SV,
url = {http://www.springerlink.com/content/xglb6gpgxtrxyfw9/?p=e96ff61b877747838964d91b17781813&pi=0},
abstract = {We investigate a special class of map labeling
problem. Let $P = \{p_1, p_2, \ldots, p_n\}$ be a
set of point sites distributed on a 2D map. A label
associated with each point is a axis-parallel
rectangle of a constant height but of variable
width. Here height of a label indicates the font
size and width indicates the number of characters in
that label. For a point $p_i$, its label contains
the point $p_i$ at its top-left or bottom-left
corner, and it does not obscure any other point in
$P$. Width of the label for each point in $P$ is
known in advance. The objective is to label the
maximum number of points on the map so that the
placed labels are mutually non-overlapping. We first
consider a simple model for this problem. Here, for
each point $p_i$, the corner specification (i.e.,
whether the point $p_i$ would appear at the top-left
or bottom-left corner of the label) is known. We
formulate this problem as finding the maximum
independent set of a chordal graph, and propose an
$O(n \log n)$ time algorithm for producing the
optimal solution. If the corner specification of the
points in $P$ is not known, our algorithm is a
2-approximation algorithm. Next, we develop a good
heuristic algorithm that is observed to produce
optimal solutions for most of the randomly generated
instances and for all the standard benchmarks
available in \cite{wwks-3rsgl-01}.}
}
@Article{rgdn-oaspl-04,
author = {Sasanka Roy and Partha P. Goswami and Sandip Das and
Subhas C. Nandy},
title = {Optimal Algorithm for a Special Point-Labeling
Problem},
journal = IPL,
year = 2004,
volume = 89,
number = 2,
pages = {91--98},
url = {http://dx.doi.org/10.1016/j.ipl.2003.10.002},
doi = {10.1016/j.ipl.2003.10.002},
abstract = {A special class of map labeling problem is
studied. Let $P = \{p_1, p_2, \dots, p_n\}$ be a set
of point sites distributed on a 2D map. A label
associated with each point pi is an axis-parallel
rectangle $r_i$ of specified width. The height of
all $r_i$, $i = 1, 2, \dots, n$ are same. The
placement of $r_i$ must contain $p_i$ at its
top-left or bottom-left corner, and it does not
obscure any other point in $P$. The objective is to
label the maximum number of points on the map so
that the placed labels are mutually
non-overlapping. We first consider a simple model
for this problem. Here, for each point $p_i$, the
corner specification (i.e., whether the point $p_i$
would appear at the top-left or bottom-left corner
of the label) is known a priori. We show that the
time complexity of this problem is $\Omega(n \log
n)$, and then propose an algorithm for this problem
which runs in $O(n \log n)$ time. If the corner
specifications of the points in $P$ are not known,
our algorithm is a 2-approximation algorithm. Here
we propose an efficient heuristic algorithm that is
easy to implement. Experimental evidences show that
it produces optimal solutions for most of the
randomly generated instances and for all the
standard benchmarks available in
http://www.math-inf.uni-greifswald.de/map-labeling/.}
}
@Article{rl-lrbpf-06,
author = {Glaydston Mattos Ribeiro and Luiz Antonio Nogueira
Lorena},
title = {Lagrangean Relaxation Bounds for Point-Feature
Cartographic Label Placement Problem},
journal = {Pesquisa Operacional},
year = 2006,
volume = 26,
number = 3,
pages = {459--471},
pdf = {http://www.lac.inpe.br/\~{}lorena/glaydston/lagclus-bounds-PFCLP.pdf}
}
@Article{rl-lrcpf-07,
author = {Glaydston Mattos Ribeiro and Luiz Antonio Nogueira
Lorena},
title = {Lagrangean relaxation with clusters for
point-feature cartographic label placement problems},
journal = {Computers and Operations Research},
year = 2007,
note = {To appear},
pdf = {http://www.lac.inpe.br/\~{}lorena/glaydston/Glaydston_Lorena_COR_Revised.PDF}
}
@Article{rl-lrcpf-08,
author = {Glaydston Mattos Ribeiro and Luiz Antonio Nogueira
Lorena},
title = {Lagrangean relaxation with clusters for
point-feature cartographic label placement problems},
journal = {Comput. Oper. Res.},
volume = 35,
number = 7,
year = 2008,
issn = {0305-0548},
pages = {2129--2140},
url = {http://dx.doi.org/10.1016/j.cor.2006.09.024},
doi = {10.1016/j.cor.2006.09.024},
}
@InBook{rmmkg-ec-95,
author = {Arthur H. Robinson and Joel L. Morrison and Phillip
C. Muehrcke and A. Jon Kimerling and Stephen
C. Guptill},
title = {Elements of Cartography},
chapter = 22,
publisher = {John Wiley \& Sons, Inc.},
year = 1995
}
@InProceedings{rshs-isi3d-03,
author = {Felix Ritter and Henry Sonnet and Knut Hartmann and
Thomas Strothotte},
title = {Illustrative Shadows: Integrating 3D and 2D
Information Displays},
booktitle = {Proceedings of Intelligent User Interfaces (IUI'03)},
pages = {166--173},
year = 2003,
month = {12--15~} # jan,
location = {Miami, Florida}
}
@PhdThesis{s-gaclp-01,
author = {Tycho Strijk},
title = {Geometric Algorithms for Cartographic Label Placement},
school = {Utrecht University, Department of Computer Science},
year = 2001,
month = jan,
pdf = MAPLABURL # {s-gaclp-01i.pdf}
}
@PhdThesis{s-npsp-95,
author = {Erik Schwarzenecker},
title = {{Ein NP-schweres Plazierungsproblem}},
school = {Technische Fakult{\"a}t der Universit{\"a}t des
Saarlandes, Saarbr{\"u}cken},
year = 1995,
language = {german},
update = {98.01 wolff}
}
@Misc{s-rfpr-95,
author = {Vasco Alexander Schmidt},
title = {{R}eine {F}orschung, praktische {R}esultate},
howpublished = {Newspaper article in \emph{Die Zeit}},
year = 1995,
number = 18,
pages = 45,
url = MAPLABURL # {s-rfpr-95.html},
postscript = MAPLABURL # {s-rfpr-95.gif},
month = {28~} # apr,
language = {german}
}
@Article{s-spps-89,
author = {Monika Sester},
title = {{SCRIBO} - ein {P}rogramm zur {P}lazierung von {S}chriften},
journal = {Nachrichten aus dem Karten- und Vermessungswesen},
series = {I},
year = 1989,
number = 103,
pages = {105--111},
publisher = {Verlag des Instituts f{\"u}r Angewandte Geod{\"a}sie},
address = {Frankfurt am Main},
language = {german},
annote = {A system for interactive grid-based name placement is
presented. SCRIBO combines cartographic needs like
placement on optionally enriched straight lines or
on circles and variation of size, colour, width,
inclination and distance of letters with a method of
interactive correction. Letter placement can be
performed either in binary or in continuous tone
mode.}
}
@InProceedings{sk-dadds-00,
author = {Ben Shneiderman and Hyunmo Kang},
title = {Direct Annotation: A Drag-and-Drop Strategy for
Labeling Photos},
booktitle = {Proc. IEEE Internat. Conf. on Information Visualisation
(IV'00)},
pages = {88--95},
year = 2000,
editor = {E. Banissi and M. Bannatyne and C. Chen and
F. Khosrowshahi and M. Sarfraz and A. Ursyn},
location = {London},
month = {19--21~} # jul,
pdf = {ftp://ftp.cs.umd.edu/pub/hcil/Reports-Abstracts-Bibliography/2000-06html/2000-06.pdf},
abstract = {Annotating photos is such a time-consuming, tedious
and error-prone data entry task that it discourages
most owners of personal photo libraries. By allowing
users to drag labels such as personal names from a
scrolling list and drop them on a photo, we believe
we can make the task faster, easier and more
appealing. Since the names are entered in a
database, searching for all photos of a friend or
family member is dramatically simplified. We
describe the user interface design and the database
schema to support direct annotation, as implemented
in our PhotoFinder prototype}
}
@TechReport{sk-lrmme-98,
author = {Tycho Strijk and Marc van Kreveld},
title = {Labeling a Rectilinear Map More Efficiently},
institution = UU,
number = {UU-CS-1998-29},
year = 1998,
pdf = {ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-1998/1998-29.pdf},
}
@Article{sk-lrmme-99,
author = {Tycho Strijk and Marc van Kreveld},
title = {Labeling a Rectilinear Map More Efficiently},
journal = IPL,
year = 1999,
volume = 69,
number = 1,
pages = {25--30},
succeeds = {pzc-ptslr-98},
abstract = {Given a rectilinear map consisting of $n$ disjoint
line segments, the corresponding labeling problem is
to place a rectangle at each segment, allowing three
possible positions, such that the rectangles do not
intersect. This problem has a decision and a height
maximization version. This paper improves results
from \cite{pzc-ptslr-98}. An algorithm is proposed
that improves the running time of the decision
problem from $O(n^2)$ to $O(n \log n \alpha(n))$,
with $\alpha(n)$ the inverse of the Ackermann
function. An algorithm for the height maximization
problem is presented that lowers the running time
from $O(n^2 \log n)$ to $O(n \log 2 n
\alpha(n))$. These bounds are for the pointer
machine model; in the RAM model we can drop the
$\alpha(n)$ factor. We also describe an algorithm to
solve the decision labeling problem where segments
of arbitrary directions are allowed in $O(n^{4/3}
\polylog n)$ time and space.}
}
@Article{sk-nbmlu-02,
author = {Michael J. Spriggs and J. Mark Keil},
title = {A New Bound for Map Labeling with Uniform Circle
Pairs},
journal = IPL,
year = 2002,
volume = 81,
number = 1,
pages = {47--53},
cites = {c-fadsi-88, dmm-pslsp-00, fw-ppalm-91, gs-pmgsc-85,
kt-ualgf-98, qwxz-na2lp-00, wtx-blb2c-00,
zp-eaaml-99, ZZZ},
succeeds = {zp-eaaml-99, qwxz-na2lp-00},
precedes = {wtx-blb2c-00},
url = {http://www.elsevier.com/gej-ng/10/23/20/85/27/34/abstract.html},
abstract = {Given a planar point set, we wish to label the
points with uniform circular labels such that each
input point lies on the boundary of two labels, none
of the interiors of the labels intersect, and the
size of the labels is maximized. This problem is
known as map-labeling with uniform circular pairs
(MLUCP) and has been shown to be NP-hard. In this
paper, we give an $O(n \log n)$ time, $O(n)$ space
algorithm that computes a labeling, such that the
diameter of the circular labels in an optimum
solution is no more than $(1+\sqrt{33})/4 \approx
1.686$ times the diameter of the labels computed by
our algorithm.}
}
@TechReport{sk-pepls-00,
author = {Tycho Strijk and Marc van Kreveld},
title = {Practical Extensions of Point Labeling in the Slider
Model},
institution = UU,
number = {UU-CS-2000-08},
year = 2000,
comment = {extends sk-pepls-99},
succeeds = {ksw-plsl-99, sk-pepls-99},
pdf = {ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-2000/2000-08.pdf},
abstract = {This paper extends on research by the authors
together with Alexander Wolff on point label
placement using a model where labels can be placed
at any position that touches the point (the slider
model). Such models have been shown to perform
better than methods that allow only a fixed number
of positions per label. The novelties in this paper
include respecting other map features that must be
avoided by the labels, and incorporating labels with
di erent height. The result is an efficient and
simple $O((n + m) \log(n + m))$ time algorithm with
a performance guarantee for label placement in the
slider model. Here $n$ is the number of points to be
labeled and $m$ is the combinatorial complexity of
the map features that must be avoided. Due to its
efficiency, the algorithm can be used in interactive
and on-line mapping.}
}
@Article{sk-pepls-02,
author = {Tycho Strijk and Marc van Kreveld},
title = {Practical Extensions of Point Labeling in the Slider
Model},
journal = {GeoInformatica},
year = 2002,
volume = 6,
number = 2,
pages = {181--197}
}
@InProceedings{sk-pepls-99,
author = {Tycho Strijk and Marc van Kreveld},
title = {Practical Extensions of Point Labeling in the Slider
Model},
booktitle = {Proc. 7th ACM Sympos. on Advances in Geographic
Information Systems},
location = {Kansas City, MO},
year = 1999,
month = {5--6~} # nov,
pages = {47--52},
succeeds = {ksw-plsl-99},
abstract = {This paper extends on research by the authors
together with Alexander Wolff on point label
placement using a model where labels can be placed
at any position that touches the point (the slider
model). Such models have been shown to perform
better than methods that allow only a fixed number
of positions per label. The earlier research on
slider models is extended here by also respecting
other map features that must be avoided by the
labels, and by incorporating labels with different
height. The result is an efficient and simple $O((n
+ m) \log(n + m))$ time algorithm with a performance
guarantee for label placement in the slider
model. Here $n$ is the number of points to be
labeled and m is the combinatorial complexity of the
map features that must be avoided. Due to its
efficiency, the algorithm can be used in interactive
and on-line mapping.}
}
@InProceedings{sr-lalpf-02,
author = {Michael Schreyer and G\"{u}nther R. Raidl},
title = {Letting Ants Labeling Point Features},
booktitle = {Proc. IEEE Congress on Evolutionary Computation
(CEC'02)},
pages = {1564--1569},
year = 2002,
editor = {D. Fogel et al.},
publisher = {IEEE Press},
pdf = {http://www.ads.tuwien.ac.at/publications/bib/pdf/schreyer-02.pdf},
abstract = {This paper describes an ant colony system (ACS) for
labeling point features. A preprocessing step
reduces the search space in a safe way. The ACS
applies local improvement and masking, a technique
that focuses the optimization on critical
regions. Empirical results indicate that the ACS
reliably identifies high-quality solutions which are
in many cases better than those of a
state-of-the-art genetic algorithm for point feature
labeling.}
}
@TechReport{sva-amisa-00,
author = {Tycho Strijk and Bram Verweij and Karen Aardal},
title = {Algorithms for Maximum Independent Set Applied to
Map Labelling},
institution = UU,
number = {UU-CS-2000-22},
year = 2000,
pdf = {ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-2000/2000-22.pdf}
}
@Article{sw-lpc-01,
author = {Tycho Strijk and Alexander Wolff},
title = {Labeling Points with Circles},
journal = IJCGA,
year = 2001,
month = apr,
volume = 11,
number = 2,
pages = {181--195},
url = {http://journals.wspc.com.sg/journals/ijcga/11/1102/S0218195901000444.html},
pdf = AWPUBURL # {sw-lpc-01.pdf},
cites = {aks-lpmis-98, c-accgc-96, cms-esapf-95,
dlss-sdakp-95, dmmmz-mlg-97, ee-innfm-94,
f-agpsp-92, fpt-opcpa-81, fw-ppalm-91, il-nhsml-97,
kr-pcr-92, kt-ualgf-98, l-pftu-82, ms-ccclp-91,
ksw-plsl-99, ws-mlb-96, wwks-3rsgl-01, ZZZ},
succeeds = {dmmmz-mlg-97, sw-lpc-99},
precedes = {dmm-pslsp-00},
abstract = {We present a new algorithm for labeling points with
circles of equal size. Our algorithm tries to
maximize the label size. It improves the
approximation factor of the only known algorithm for
this problem by more than 50~\% to about 1/20. At
the same time, our algorithm keeps the $O(n \log n)$
time bound of its predecessor. In addition, we show
that the decision problem is NP-hard and that it is
NP-hard to approximate the maximum label size beyond
a certain constant factor.},
update = {wolff 06.00}
}
@TechReport{sw-lpc-99,
author = {Tycho Strijk and Alexander Wolff},
title = {Labeling Points with Circles},
institution = {Institut f{\"u}r Informatik, Freie Universit{\"a}t Berlin},
year = 1999,
number = {B 99-08},
month = apr,
precedes = {sw-lpc-01},
abstract = {We present a new algorithm for labeling points with
circles of equal size. Our algorithm maximizes the
label size. It improves the approximation factor of
the only known algorithm for this problem by more
than 50~\% to about 1/20. At the same time, our
algorithm keeps the $O(n \log n)$ time bound of its
predecessor. In addition, we show that the decision
problem is NP-hard and that it is NP-hard to
approximate the maximum label size beyond a certain
constant factor.}
}
@InProceedings{t-dlsfm-00,
author = {Junichi Tatemura},
title = {Dynamic Label Sampling on Fisheye Maps for
Information Exploration},
booktitle = {Proc. Advanced Visual Interfaces (AVI'00)},
year = 2000,
pdf = {http://portal.acm.org/ft_gateway.cfm?id=345325&type=pdf&coll=GUIDE&dl=ACM&CFID=13982954&CFTOKEN=5010775}
}
@InProceedings{tb-pppls-04,
author = {{\'E}ric D. Taillard and Gregory Burri},
title = {{POPMUSIC} pour le placement de l{\'e}gende sur des
plans},
booktitle = {Actes de Francoro 4},
pages = {95--97},
year = 2004,
editor = {{\'E}. D. Taillard and Ph. Waelti and M. Widmer},
confmonth = aug,
location = {Fribourg, Switzerland},
pdf = {http://mistic.heig-vd.ch/taillard/articles.dir/francoro_etiquettes.pdf}
}
@InProceedings{twx-nabp2-00,
author = {Michael Thon and Alexander Wolff and Yinfeng Xu},
title = {Ein neuer {A}lgorithmus zur {B}eschriftung von
{P}unkten mit je zwei {K}reisen},
booktitle = {Tagungsband der Informatiktage'00},
pages = { },
year = 2000,
editor = {{Gesellschaft f{\"u}r Informatik e.V.}},
month = {27--28~} # oct,
location = {Neues Kloster, Bad Schussenried},
language = {german},
cites = {as-dssga-99, a-vdsfg-91 dmm-pslsp-00, i-ank-62
kt-mlpp-98, qwxz-na2lp-00, sw-lpc-01, zp-eaaml-99,
ZZZ},
precedes = {wtx-blb2c-00}
}
@TechReport{v-apafn-94,
author = {Aruna Ashtakala Vedula},
title = {Automatic Positioning of Area-Feature Names on
Special Purpose Maps},
institution = {Department of Electrical and Computer Engineering,
Rutgers University},
year = 1994,
number = {CE-101}
}
@InProceedings{va-oamis-99,
author = {Bram Verweij and Karen Aardal},
title = {An Optimisation Algorithm for Maximum Independent
Set with Applications in Map Labelling},
editor = {J. Ne{\v s}et{\v r}il},
series = LNCS,
publisher = SV,
volume = 1643,
booktitle = {Proc. 7th Annu. European Sympos. Algorithms (ESA'99)},
year = 1999,
location = {Prague},
confmonth = {16--18~} # jul,
pages = {426--437},
doi = {10.1007/3-540-48481-7_38}
}
@Article{vws-ptlmd-97,
author = {Oleg Verner and Roger Wainwright and Dale
Schoenefeld},
title = {Placing Text Labels on Maps and Diagrams using
Genetic Algorithms with Masking},
journal = {INFORMS J. Computing},
year = 1997,
volume = 9,
number = 3,
pages = {266--275}
}
@TechReport{w-acpft-97,
author = {Jun Wang},
title = {Automated Cartographic Point-Feature Text Placement},
institution = {Department of Electrical and Computer Enginering,
Rutgers University, Piscataway, NJ},
year = 1997
}
@PhdThesis{w-alptp-99,
author = {Alexander Wolff},
title = {Automated Label Placement in Theory and Practice},
school = FU,
year = 1999,
month = may,
annote = {general labeling algorithm based on a CSP
formulation, experimental comparison of various
point labeling algorithms, point label algorithm
for circular labels, line labeling algorithm that
allows curved labels, generic design of geometric
algorithms},
pdf = AWPUBURL # {w-alptp-99.pdf}
}
@TechReport{w-amlio-93,
author = {Frank Wagner},
title = {Approximate Map Labeling is in ${\Omega}(n \log n)$},
institution = FU,
year = 1993,
number = {B 93-18},
month = dec,
postscript = {ftp://ftp.inf.fu-berlin.de/pub/reports/tr-b-93-18.ps.gz}
}
@Article{w-amlon-94,
author = {Frank Wagner},
title = {Approximate Map Labeling is in ${\Omega}(n \log n)$},
journal = IPL,
year = 1994,
volume = 52,
number = 3,
pages = {161--165},
doi = {http://dx.doi.org/10.1016/0020-0190(94)90001-9}
}
@MastersThesis{w-ccnp-73,
author = {W.T. Wilkie},
title = {Computerized Cartographic Name Processing},
school = {Department of Electrical Engineering, University of
Saskatchewan, Canada},
year = 1973
}
@Article{w-digtp-00,
author = {Clifford H. Wood},
title = {A Descriptive and Illustrated Guide for Type
Placement on Small Scale Maps},
journal = {The Cartographic Journal},
year = 2000,
volume = 37,
number = 1,
pages = {5--18},
month = jun
}
@MastersThesis{w-ml-95,
author = {Alexander Wolff},
title = {Map Labeling},
school = FU,
year = 1995,
month = may,
postscript = AWPUBURL # {w-ml-95.ps.gz}
}
@TechReport{w-spnph-00,
author = {Alexander Wolff},
title = {A Simple Proof for the {NP}-Hardness of Edge Labeling},
institution = UG,
year = 2000,
number = {11/2000},
month = sep,
url = {http://www.math-inf.uni-greifswald.de/preprints/shadow/wolff00_11.rdf.html},
pdf = {http://www.math-inf.uni-greifswald.de/pub/full/prep/2000/wolff00_11.pdf},
pdf2 = AWPUBURL # {w-spnph-00.pdf},
keywords = {complexity theory, graph drawing, computational
geometry, label placement},
abstract = {Kakoulis and Tollis have shown that labeling the
edges of a graph drawing with axis-parallel
rectangles is NP-hard \cite{kt-elpp-97}. In this
note we simplify their proof by reducing from planar
3-SAT instead of 3-SAT.},
cites = {af-aesam-84, c-accgc-96, cms-esapf-95, df-esdmn-89,
dkmt-elglt-98, dmmmz-mlg-97, ecms-gcla-97,
fw-ppalm-91, h-aanpa-82, il-nhsml-97, kr-pcr-92,
kt-alehd-97, kt-elpp-97, kt-mlpp-98, kt-ualgf-98,
l-pftu-82, m-ctcc-80, ms-ccclp-91, nh-mlagl-00,
sw-lpc-99, sw-lpc-01, ksw-plsl-99, ws-mlb-96,
ww-pmla-97, wwks-3rsgl-01, z-sl01i-90, ZZZ}
}
@MastersThesis{w-vrnpm-90,
author = {Chyan Victor Wu},
title = {Verification of Rules for Name Placement of Maps},
school = {Department of Geography, State University of New
York at Buffalo, New York},
year = 1989
}
@Article{wb-rrpfn-91,
author = {Chyan Victor Wu and Barbara Pfeil Buttenfield},
title = {Reconsidering Rules for Point-Feature Name
Placement},
journal = {Cartographica},
year = 1991,
volume = 28,
number = 1,
pages = {10--27},
precedes = {m-pcnpd-94}
}
@Misc{wdszcf-saia-01,
author = {Liu Wenyin and Susan Dumais and Yanfeng Sun and
HongJiang Zhang and Mary Czerwinski and Brent Field},
title = {Semi-Automatic Image Annotation},
howpublished = {Microsoft Strategy Paper?},
year = {2001?},
keywords = {image annotation, image retrieval, relevance
feedback, image database, user study, performance
evaluation},
pdf = {http://www.research.microsoft.com/users/marycz/semi-auto-annotatoin--full.pdf},
abstract = {A novel approach to semi-automatically and
progressively annotating images with keywords is
presented. The progressive annotation process is
embedded in the course of integrated keyword-based
and content-based image retrieval and user
feedback. When the user submits a keyword query and
then provides relevance feedback, the search
keywords are automatically added to the images that
receive positive feedback and can then facilitate
keyword-based image retrieval in the future. The
coverage and quality of image annotation in such a
database system is improved progressively as the
cycle of search and feedback increases. The strategy
of semi-automatic image annotation is better than
manual annotation in terms of efficiency and better
than automatic annotation in terms of accuracy. A
performance study is presented which shows that high
annotation coverage can be achieved with this
approach, and a preliminary user study is described
showing that users view annotations as important and
will likely use them in image retrieval. The user
study also suggested user interface enhancements
needed to support relevance feedback. We believe
that similar approaches could also be applied to
annotating and managing other forms of multimedia
objects.}
}
@Article{wka-appma-94,
author = {Gerald Weber and Lars Knipping and Helmut Alt},
title = {An Application of Point Pattern Matching in
Astronautics},
journal = {Journal of Symbolic Computation},
year = 1994,
volume = 17,
pages = {321--340}
}
@InCollection{wkksa-seahq-00,
author = {Alexander Wolff and Lars Knipping and Marc van
Kreveld and Tycho Strijk and Pankaj K. Agarwal},
title = {A Simple and Efficient Algorithm for High-Quality
Line Labeling},
booktitle = {Innovations in GIS VII: GeoComputation},
publisher = TF,
year = 2000,
editor = {Peter M. Atkinson and David J. Martin},
chapter = 11,
pages = {147--159},
pdf = AWPUBURL # {wkksa-seahq-00.pdf}
}
@TechReport{wkksa-seahq-01,
author = {Alexander Wolff and Lars Knipping and Marc van
Kreveld and Tycho Strijk and Pankaj K. Agarwal},
title = {A Simple and Efficient Algorithm for High-Quality
Line Labeling},
institution = UU,
number = {UU-CS-2001-44},
year = 2001,
pdf = {ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-2001/2001-44.pdf}
}
@InProceedings{wkksa-seahq-99,
author = {Alexander Wolff and Lars Knipping and Marc van
Kreveld and Tycho Strijk and Pankaj K. Agarwal},
title = {A Simple and Efficient Algorithm for High-Quality
Line Labeling},
booktitle = {Proc. GIS Research UK 7th Annual Conf.
(GISRUK'99)},
year = 1999,
editor = {David Martin and Fulong Wu},
pages = {146--150},
location = {Southampton},
month = {14--16~} # apr,
organization = {Department of Geography, University of Southampton}
}
@InProceedings{wmpeft-dvgel-05,
author = {Pak Chung Wong and Patrick Mackey and Ken Perrine
and James Eagan and Harlan Foote and Jim Thomas},
title = {Dynamic Visualization of Graphs with Extended
Labels},
booktitle = {Proc. IEEE Symp. Information Visualization
(InfoVis'05)},
pages = {73--80},
year = 2005,
url = {http://dx.doi.org/10.1109/INFOVIS.2005.11},
doi = {10.1109/INFOVIS.2005.11},
location = {Minneapolis, MN},
confmonth = {23--25~} # oct
}
@Misc{ws-mlb-96,
author = {Alexander Wolff and Tycho Strijk},
title = {{The Map-Labeling Bibliography}},
howpublished = {\url{http://i11www.ira.uka.de/map-labeling/bibliography}},
year = 1996,
url = MAPLABBIB
}
@InProceedings{wtx-blb2c-00,
author = {Alexander Wolff and Michael Thon and Yinfeng Xu},
title = {A Better Lower Bound for Two-Circle Point Labeling},
booktitle = {Proc. 11th Annu. Internat. Sympos.
Algorithms Comput. (ISAAC'00)},
year = 2000,
editor = {D.T. Lee},
series = LNCS,
publisher = SV,
volume = 1969,
pages = {422--431},
location = {Taipei},
organization = {Institute of Information Science, Academia Sinica},
month = {18--20~} # dec,
pdf = AWPUBURL # {wtx-blb2c-00.pdf},
cites = {af-aesam-84, as-dssga-99, a-vdsfg-91, c-accgc-96,
cms-esapf-95, df-esdmn-89, dmmmz-mlg-97,
dmm-pslsp-00, fw-ppalm-91, h-aanpa-82, ksy-p2dcp-99,
ksy-lrmsl-99, kt-mlpp-98, m-ctcc-80, qwxz-na2lp-00,
sw-lpc-01, ksw-plsl-99, ws-mlb-96, ww-pmla-97,
z-sl01i-90, zp-eaaml-99, ZZZ},
succeeds = {kt-mlpp-98, zp-eaaml-99, zq-naaml-02, qwxz-na2lp-00},
precedes = {wtx-sf23a-02},
abstract = {Given a set $P$ of $n$ points in the plane, the
two-circle point-labeling problem consists of
placing $2n$ uniform, non-intersecting,
maxi\-mum-size open circles such that each point
touches exactly two circles. It is known that it is
NP-hard to approximate the label size beyond a
factor of $\approx 0.7321$. In this paper we improve
the best previously known approximation factor from
$\approx 0.51$ to $2/3$. We keep the $O(n \log n)$
time and $O(n)$ space bounds of the previous
algorithm. As in the previous algorithm we label
each point within its Voronoi cell. Unlike that
algorithm we explicitely compute the Voronoi
diagram, label each point \emph{optimally} within
its cell, compute the smallest label diameter over
all points and finally shrink all labels to this
size.}
}
@Article{wtx-sf23a-02,
author = {Alexander Wolff and Michael Thon and Yinfeng Xu},
title = {A Simple Factor-2/3 Approximation Algorithm for
Two-Circle Point Labeling},
journal = IJCGA,
year = 2002,
volume = 12,
number = 4,
pages = {269--281},
pdf = AWPUBURL # {wtx-sf23a-02.pdf},
cites = {af-aesam-84, agss-ltacv-89, a-vdsfg-91,
bckm-ap2cc-98, c-cgitf-99, cms-esapf-95,
df-esdmn-89, dmmmz-mlg-97, dmm-pslsp-00,
fw-ppalm-91, h-aanpa-82, ksy-lrmsl-99, kt-mlpp-98,
m-ctcc-80, ocon-nlaic-82, qwxz-na2lp-00, sw-lpc-01,
ksw-plsl-99, ws-mlb-96, wtx-blb2c-00, ww-pmla-97,
z-sl01i-90, zp-eaa2l-01, ZZZ},
succeeds = {wtx-blb2c-00},
abstract = {Given a set $P$ of $n$ points in the plane, the
two-circle point-labeling problem consists of
placing $2n$ uniform, non-intersecting, maximum-size
open circles such that each point touches exactly
two circles.
\par
It is known that this problem is NP-hard to
approximate. In this paper we give a simple
algorithm that improves the best previously known
approximation factor from $4/(1+\sqrt{33}) \approx
0.5931$ to 2/3. The main steps of our algorithm are
as follows. We first compute the Voronoi diagram,
then label each point \emph{optimally} within its
cell, compute the smallest label diameter over all
points and finally shrink all labels to this
size. We keep the $O(n \log n)$ time and $O(n)$
space bounds of the previously best algorithm.}
}
@InProceedings{ww-cfml-98,
author = {Frank Wagner and Alexander Wolff},
title = {A Combinatorial Framework for Map Labeling},
booktitle = {Proc. Symp. 6th Internat. Symp. on Graph Drawing (GD'98)},
editor = {Sue H. Whitesides},
series = LNCS,
publisher = SV,
volume = 1547,
pages = {316--331},
year = 1998,
month = {13--15~} # aug,
location = {Montr{\'e}al},
postscript = AWPUBURL # {ww-cfml-98.ps.gz},
abstract = {The general map labeling problem consists in
labeling a set of sites (points, lines, regions)
given a set of candidates (rectangles, circles,
ellipses, irregularly shaped labels) for each
site. A map can be a classical cartographical map, a
diagram, a graph or any other figure that needs to
be labeled. A labeling is either a complete set of
non-conflicting candidates, one per site, or a
subset of maximum cardinality. Finding such a
labeling is NP-hard. We present a combinatorial
framework to attack the problem in its full
generality. The key idea is to separate the
geometric from the combinatorial part of the
problem. The latter is captured by the conflict
graph of the candidates and by rules which
successively simplify this graph towards a
near-optimal solution. We exemplify this framework
at the problem of labeling point sets with
axis-parallel rectangles as candidates, four per
point. We do this such that it becomes clear how our
concept can be applied to other cases. We study
competing algorithms and do a thorough empirical
comparison. The new algorithm we suggest is fast,
simple and effective.},
url = {http://link.springer.de/link/service/series/0558/tocs/t1547.htm}
}
@InProceedings{ww-eeaam-95,
author = {Frank Wagner and Alexander Wolff},
title = {An Efficient and Effective Approximation Algorithm
for the Map Labeling Problem},
booktitle = {Proc. 3rd Annu. European Sympos. Algorithms (ESA'95)},
editor = {Paul Spirakis},
series = LNCS,
volume = 979,
publisher = SV,
year = 1995,
month = {25--27~} # sep,
location = {Corfu},
pages = {420--433},
postscript = AWPUBURL # {ww-eeaam-95.ps.gz},
abstract = {We present an algorithm for the Map Labeling
problem that guarantees optimal approximation
quality and runtime behaviour, and yields results
closer to the optimum than the best heuristic
known so far.
\par
The sample data used in the experimental
evaluation consists of three different classes of
random problems and a selection of problems
arising in the production of groundwater quality
maps by the authorities of the City of Munich.},
update = {97.07 agarwal, 97.03 gaertner+salinger, 98.01 wolff}
}
@InProceedings{ww-frml-95,
author = {Frank Wagner and Alexander Wolff},
title = {Fast and Reliable Map Labeling},
booktitle = {Proc. 9th Internat. Sympos. on Computer Science for
Environment Protection (CSEP'95)},
year = 1995,
confmonth = {27--29~} # sep,
location = {Berlin},
pages = {667--675},
publisher = {Metropolis},
update = {97.03 gaertner+salinger, 98.01 wolff},
postscript = AWPUBURL # {ww-frml-95.ps.gz}
}
@InProceedings{ww-mlhpg-95,
author = {Frank Wagner and Alexander Wolff},
title = {Map Labeling Heuristics: {Provably} Good and
Practically Useful},
booktitle = {Proc. 11th Annu. ACM Sympos. Comput. Geom. (SoCG'95)},
year = 1995,
confmonth = {5--7~} # jun,
location = {Vancouver},
pages = {109--118},
keywords = {experimental, approximation algorithm},
update = {95.09 mitchell, 98.01 wolff},
postscript = AWPUBURL # {ww-mlhpg-95.ps.gz},
abstract = {The lettering of maps is a classical problem of
cartography that consists of placing names, symbols,
or other data near to specified sites on a
map. Certain design rules have to be obeyed. A
practically interesting special case, the Map
Labeling problem, consists of placing axis parallel
rectangular labels of common size so that one of its
corners is the site, no two labels overlap, and the
labels are of maximum size in order to have legible
inscriptions. The problem is NP-hard; it is even
NP-hard to approximate the solution with quality
guaranty better than 50 percent. There is an
approximation algorithm $A$ with a quality guaranty
of 50 percent and running time $O(n \log n)$. So $A$
is the best possible algorithm from a theoretical
point of view. This is even true for the running
time, since there is a lower bound on the running
time of any such approximation algorithm of $\Omega
(n \log n)$. Unfortunately $A$ is useless in
practice as it typically produces results that are
intolerably far off the maximum size. The main
contribution of this paper is the presentation of a
heuristical approach that has $A$'s advantages while
avoiding its disadvantages: 1. It uses $A$'s result
in order to guaranty the same optimal running time
efficiency; a method which is new as far as we
know. 2. Its practical results are close to the
optimum. The practical quality is analysed by
comparing our results to the exact optimum, where
this is known; and to lower and upper bounds on the
optimum otherwise. The sample data consists of three
different classes of random problems and a selection
of problems arising in the production of groundwater
quality maps by the authorities of the City of
Munich.}
}
@TechReport{ww-mlhpg-95t,
author = {Frank Wagner and Alexander Wolff},
title = {Map Labeling Heuristics: {Provably} Good and
Practically Useful},
institution = {Institut f{\"u}r Informatik, Freie Universit{\"a}t
Berlin},
year = 1995,
number = {B 95-04},
month = apr,
postscript = {ftp://ftp.inf.fu-berlin.de/pub/reports/tr-b-95-04.ps.gz}
}
@Article{ww-pmla-97,
author = {Frank Wagner and Alexander Wolff},
title = {A Practical Map Labeling Algorithm},
journal = CGTA,
year = 1997,
volume = 7,
pages = {387--404},
update = {98.01 wolff},
postscript = AWPUBURL # {ww-pmla-97.ps.gz},
abstract = {The Map Labeling problem is a classical
problem of cartography. There is a theoretically
optimal approximation algorithm $A$. Unfortunately
$A$ is useless in practice as it typically
produces results that are intolerably far off the
optimal size. On the other hand there are
heuristics with good practical results.
\par
In this paper we present an algorithm $B$ that
(a) guarantees the optimal approximation
quality and runtime behaviour of $A$, and
(b) yields results significantly closer to
the optimum than the best heuristic known so far.
\par
The sample data used in the experimental
evaluation consists of three different classes of
random problems and a selection of problems
arising in the production of groundwater quality
maps by the authorities of the City of Munich.}
}
@Article{wwks-3rsgl-01,
author = {Frank Wagner and Alexander Wolff and Vikas Kapoor
and Tycho Strijk},
title = {Three Rules Suffice for Good Label Placement},
journal = {Algorithmica},
volume = 30,
number = 2,
year = 2001,
pages = {334--349},
cites = {aks-lpmis-97, cms-esapf-95, dmmmz-mlg-97,
fw-ppalm-91, fpt-opcpa-81, f-esapn-88, h-aanpa-82,
i-pnm-75, kt-ualgf-98, kr-pcr-92, nm-lledt-90,
sk-pepls-99, ksw-plsl-99, w-amlio-94, ww-pmla-97,
ww-cfml-98, w-lptp-99, wb-rrpfn-91, ZZZ},
abstract = {The general label-placement problem consists in
labeling a set of features (points, lines, regions)
given a set of candidates (rectangles, circles,
ellipses, irregularly shaped labels) for each
feature. The problem arises when annotating
classical cartographical maps, diagrams, or graph
drawings. The size of a labeling is the number of
features that receive pairwise nonintersecting
candidates. Finding an optimal solution, i.e.\ a
labeling of maximum size, is NP-hard.
\par
We present an approach to attack the problem in its
full generality. The key idea is to separate the
geometric part from the combinatorial part of the
problem. The latter is captured by the conflict
graph of the candidates. We present a set of rules
that simplify the conflict graph without reducing
the size of an optimal solution. Combining the
application of these rules with a simple heuristic
yields near-optimal solutions.
\par
We study competing algorithms and do a thorough
empirical comparison on point-labeling data. The
new algorithm we suggest is fast, simple, and
effective.},
pdf = AWPUBURL # {wwks-3rsgl-01.pdf}
}
@Article{y-laml-72,
author = {Pinhas Yoeli},
title = {The Logic of Automated Map Lettering},
journal = {The Cartographic Journal},
volume = 9,
year = 1972,
pages = {99--108},
update = {97.11}
}
@Article{ycl-tshpf-02,
author = {Missae Yamamoto and Gilberto Cam{\^a}ara and Luiz
Antonio Nogueira Lorena},
title = {Tabu Search Heuristic for Point-Feature Cartographic
Label Placement},
journal = {GeoInformatica},
volume = 6,
number = 1,
year = 2002,
pages = {77--90},
url = {http://www.lac.inpe.br/\~{}lorena/missae/},
pdf = {http://www.lac.inpe.br/\~{}lorena/missae/tabu.pdf},
url2 = {http://ipsapp008.lwwonline.com/ips/frames/toc.asp?J=4719&I=21},
pdf2 = {http://ipsapp008.lwwonline.com/content/getfile/4719/21/5/fulltext.pdf},
succeeds = {ylc-tsapf-99}
}
@InProceedings{yl-cgapf-03,
author = {Missae Yamamoto and Luiz Antonio Nogueira Lorena},
title = {A Constructive Genetic Approach to Point-Feature
Cartographic Label Placement},
booktitle = {Proc. Fifth Metaheuristics Internat. Conf.
(MIC'03)},
pages = {84/1--7},
year = 2003,
location = {Kyoto, Japan},
month = {25--28~} # aug,
url = {http://www.lac.inpe.br/\~{}lorena/instancias.html},
pdf = {http://www.lac.inpe.br/\~{}lorena/mic2003/cga-PFLP.pdf}
}
@InCollection{yl-cgapf-05,
author = {Missae Yamamoto and Luiz Antonio Nogueira Lorena},
title = {A Constructive Genetic Approach to Point-Feature
Cartographic Label Placement},
booktitle = {Metaheuristics: Progress as Real Problem Solvers},
pages = {285--300},
publisher = {Kluwer},
year = 2005,
editor = {T. Ibaraki and K. Nonobe and M. Yagiura}
}
@InProceedings{ylc-tsapf-99,
author = {Missae Yamamoto and Luiz Antonio Nogueira Lorena and
Gilberto Cam{\^a}ara},
title = {Tabu Search Application for Point Features
Cartographic Label Placement Problems},
booktitle = {Proc. Third Metaheuristics Internat.
Conf. (MIC'99)},
year = 1999,
month = {19--22~} # jul,
location = {Angra dos Reis},
pdf = {http://www.lac.inpe.br/\~{}lorena/proceed2e.pdf},
preceeds = {ycl-tshpf-02}
}
@Article{z-esmlp-91,
author = {Steven Zoraster},
title = {Expert Systems and the Map Label Placement Problem},
journal = {Cartographica},
year = 1991,
volume = 28,
number = 1,
pages = {1--9},
url = {http://www.szoraster.com/Cartography/ExpertSystems.htm},
update = {98.06 wolff}
}
@Article{z-ipaml-86,
author = {Steven Zoraster},
title = {Integer Programming Applied to the Map Label
Placement Problem},
journal = {Cartographica},
volume = 23,
number = 3,
year = 1986,
pages = {16--27},
update = {97.11 kreveld}
}
@Article{z-prusa-97,
author = {Steven Zoraster},
title = {Practical Results Using Simulated Annealing for
Point Feature Label Placement},
journal = {Cartography and GIS},
year = 1997,
volume = 24,
number = 4,
pages = {228--238},
url = {http://www.szoraster.com/Cartography/PracticalExperience.htm},
update = {98.06 wolff}
}
@Article{z-sl01i-90,
author = {Steven Zoraster},
title = {The Solution of Large 0-1 Integer Programming
Problems Encountered in Automated Cartography},
journal = {Operations Research},
year = 1990,
volume = 38,
number = 5,
pages = {752--759},
update = {98.01 wolff}
}
@InProceedings{zb-pemlp-87,
author = {Steven Zoraster and Stephen Bayer},
title = {Practical Experience with a Map Label Placement
Program},
booktitle = {Proc. Auto-Carto 8},
year = 1987,
pages = {701--708},
pdf = {http://www.mapcontext.com/autocarto/proceedings/auto-carto-8/pdf/practical-experience-with-a-map-label-placement-algorithm.pdf}
}
@Article{zh-ptils-06,
author = {Qingnian Zhang and Lars Harrie},
title = {Placing Text and Icon Labels Simultaneously: A
Real-Time Method},
journal = {Cartography and Geographic Information Science},
year = 2006,
volume = 33,
number = 1,
pages = {53--64},
url = {http://dx.doi.org/10.1559/152304006777323127}
}
@InProceedings{zh-rtmlp-04,
author = {Qingnian Zhang and Lars Harrie},
title = {Real-Time Map Labelling for Personal Navigation},
booktitle = {Proc. 12th Internat. Conf. Geoinformatics},
pages = {39--46},
year = 2004,
location = {G{\"a}vle, Sweden},
confmonth = {7--9~} # jun,
pdf = { },
abstract = {This paper aims to examine real-time map labelling
methods for personal navigation using small-display
mobile devices such as PDAs. It's essential to label
roads, landmarks, and other important features on
navigational maps, which will help users to
understand their location and the environment. This
paper proposes a method to label both line and point
features using a slider model, which makes it
possible to choose label positions from infinite
search space. We implemented this method in a Java
environment. A case study shows sound cartographic
results of the labelling.}
}
@Article{zm-ctlsp-06,
author = {Binhai Zhu and Minghui Jiang},
title = {A combinatorial theorem for labeling squares with
points and its application},
journal = {Journal of Combinatorial Optimization},
year = 2006,
volume = 11,
number = 4,
pages = {411--420},
url = {http://dx.doi.org/10.1007/s10878-006-8461-6}
}
@Article{zp-eaa2l-01,
author = {Binhai Zhu and Chung Keung Poon},
title = {Efficient Approximation Algorithms for Two-Label
Point Labeling},
journal = IJCGA,
year = 2001,
jourmonth = aug,
volume = 11,
number = 4,
pages = {455--464},
keywords = {approximation algorithms, map labeling, NP-hardness},
url = {http://journals.wspc.com.sg/journals/ijcga/11/1104/S0218195901000584.html},
pdf = {http://journals.wspc.com.sg/journals/ijcga/11/preserved-docs/1104/S0218195901000584.pdf},
abstract = {In this paper we propose and study two practical
variations of the map labeling problem: Given a set
$S$ of $n$ distinct (point) sites in the plane,
label each site with: (1) a pair of non-intersecting
squares of maximum possible size, (2) a pair of
non-intersecting circles of maximum possible size
(all the squares and circles are topologically open
and are of uniform size). Almost nothing has been
done before in this aspect, i.e., multi-label map
labeling. We obtain constant-factor approximation
algorithms for these problems. We also study
bicriteria approximation schemes for these problems
under a mild condition.}
}
@InProceedings{zp-eaaml-99,
author = {Binhai Zhu and Chung Keung Poon},
title = {Efficient Approximation Algorithms for Multi-Label
Map Labeling},
booktitle = {Proc. 10th Annu. Internat. Sympos.
Algorithms Comput. (ISAAC'99)},
editor = {A. Aggarwal and C. Pandu Rangan},
year = 1999,
pages = {143--152},
confmonth = {16--18~} # dec,
location = {Chennai, India},
series = LNCS,
volume = 1741,
publisher = SV,
url = {http://link.springer.de/link/service/series/0558/tocs/t1741.htm},
precedes = {zp-eaa2l-01, zq-naaml-02, qwxz-na2lp-00, wtx-blb2c-00}
}
@Article{zq-naaml-02,
author = {Binhai Zhu and Zhongping Qin},
title = {New Approximation Algorithms for Map Labeling with
Sliding Labels},
journal = {Journal of Combinatorial Optimization},
year = 2002,
volume = 6,
number = 1,
pages = {99--110},
keywords = {approximation algorithms, map labeling, NP-hardness},
succeeds = {kt-mlpp-98, zp-eaaml-99},
precedes = {qwxz-na2lp-00},
url = {http://www.kluweronline.com/issn/1382-6905},
pdf = {http://ipsapp007.lwwonline.com/content/getfile/4883/20/7/fulltext.pdf},
abstract = {In this paper we present approximation algorithm for
the following NP-hard map labeling problem: Given a
set $S$ of $n$ distinct sites in the plane, one
needs to place at each site a uniform square of
maximum possible size such that all the squares are
along the same direction. This generalizes the
classical problem of labeling points with
axis-parallel squares and restricts the most general
version where the squares can have different
orientations. We obtain a $5\sqrt{2}$-factor
approximation algorithm for this problem. This
algorithm also works for two generalized versions of
the problem. We also revisit the problem of labeling
each point with maximum uniform axis-parallel square
pairs and improve the previous approximation factor
of 4 to 3.}
}
% =====EOF ===================================================================