% ============================================================================= % 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 ===================================================================