{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T11:23:37Z","timestamp":1770981817662,"version":"3.50.1"},"reference-count":37,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2017,11,6]],"date-time":"2017-11-06T00:00:00Z","timestamp":1509926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Map labeling is a classical problem of cartography that has frequently been approached by combinatorial optimization. Given a set of features in a map and for each feature a set of label candidates, a common problem is to select an independent set of labels (that is, a labeling without label\u2013label intersections) that contains as many labels as possible and at most one label for each feature. To obtain solutions of high cartographic quality, the labels can be weighted and one can maximize the total weight (rather than the number) of the selected labels. We argue, however, that when maximizing the weight of the labeling, the influences of labels on other labels are insufficiently addressed. Furthermore, in a maximum-weight labeling, the labels tend to be densely packed and thus the map background can be occluded too much. We propose extensions of an existing model to overcome these limitations. Since even without our extensions the problem is NP-hard, we cannot hope for an efficient exact algorithm for the problem. Therefore, we present a formalization of our model as an integer linear program (ILP). This allows us to compute optimal solutions in reasonable time, which we demonstrate both for randomly generated point sets and an existing data set of cities. Moreover, a relaxation of our ILP allows for a simple and efficient heuristic, which yielded near-optimal solutions for our instances.<\/jats:p>","DOI":"10.3390\/ijgi6110342","type":"journal-article","created":{"date-parts":[[2017,11,6]],"date-time":"2017-11-06T11:39:38Z","timestamp":1509968378000},"page":"342","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Beyond Maximum Independent Set: An Extended Integer Programming Formulation for Point Labeling"],"prefix":"10.3390","volume":"6","author":[{"given":"Jan-Henrik","family":"Haunert","sequence":"first","affiliation":[{"name":"Institute of Geodesy and Geoinformation, University of Bonn, 53115 Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, 97074 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,11,6]]},"reference":[{"key":"ref_1","unstructured":"Atkinson, P.M., and Martin, D.J. (2000). A Simple and Efficient Algorithm for High-Quality Line Labeling. Innovations in GIS VII: GeoComputation, Taylor & Francis. Chapter 11."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1179\/1743277414Y.0000000091","article-title":"A Practical Algorithm for the External Annotation of Area Features","volume":"54","author":"Rylov","year":"2017","journal-title":"Cartogr. J."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Haunert, J.H., and Wolff, A. (2016, January 12\u201319). Beyond Maximum Independent Set: An Extended Model for Point-Feature Label Placement. Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXIII ISPRS Congress, Prague, Czech Republic.","DOI":"10.5194\/isprsarchives-XLI-B2-109-2016"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"16","DOI":"10.3138\/9258-63QL-3988-110H","article-title":"Integer Programming Applied to the Map Label Placement Problem","volume":"23","author":"Zoraster","year":"1986","journal-title":"Cartographica"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","article-title":"Label Placement by Maximum Independent Set in Rectangles","volume":"11","author":"Agarwal","year":"1998","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_6","first-page":"229","article-title":"A Lagrangean Decomposition for the Maximum Independent Set Problem Applied to Map Labeling","volume":"11","author":"Ribeiro","year":"2011","journal-title":"Oper. Res."},{"key":"ref_7","unstructured":"Bertin, J. (1983). Semiology of Graphics: Diagrams, Networks, Maps, The University of Wisconsin Press. [1st ed.]."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"22","DOI":"10.14714\/CP60.230","article-title":"Automation and the Map Label Placement Problem: A Comparison of Two GIS Implementations of Label Placement","volume":"60","author":"Kern","year":"2008","journal-title":"Cartogr. Perspect."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"52","DOI":"10.3138\/carto.49.1.2137","article-title":"A Comprehensive Multi-criteria Model for High Cartographic Quality Point-Feature Label Placement","volume":"49","author":"Rylov","year":"2014","journal-title":"Cartographica"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Formann, M., and Wagner, F. (1991, January 10\u201312). A Packing Problem with Applications to Lettering of Maps. Proceedings of the 7th Annual ACM Symposium on Computation Geometry (SoCG\u201991), North Conway, NH, USA.","DOI":"10.1145\/109648.109680"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"J\u00fcnger, M., and Reinelt, G. (2013). Mixed Integer Programming: Analyzing 12 Years of Progress. Facets of Combinatorial Optimization: Festschrift for Martin Gr\u00f6tschel, Springer.","DOI":"10.1007\/978-3-642-38189-8"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Nemhauser, G.L., and Wolsey, L. (1988). Integer and Combinatorial Optimization, John Wiley & Sons.","DOI":"10.1002\/9781118627372"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1179\/caj.1972.9.2.99","article-title":"The Logic of Automated Map Lettering","volume":"9","author":"Yoeli","year":"1972","journal-title":"Cartogr. J."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1559\/152304075784313304","article-title":"Positioning Names on Maps","volume":"2","author":"Imhof","year":"1975","journal-title":"Am. Cartogr."},{"key":"ref_15","unstructured":"Alinhac, G. (1962). Cartographie Th\u00e9orique et Technique, Institut G\u00e9ographique National. Chapter IV."},{"key":"ref_16","unstructured":"Doerschler, J.S., and Freeman, H. (1989, January 2\u20137). An Expert System for Dense-Map Name Placement. Proceedings of the 9th International Symposium on Computer-Assisted Cartography (Auto-Carto 9), Baltimore, MD, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1287\/opre.38.5.752","article-title":"The Solution of Large 0\u20131 Integer Programming Problems Encountered in Automated Cartography","volume":"38","author":"Zoraster","year":"1990","journal-title":"Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Verweij, B., and Aardal, K. (1999). An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling. Proceedings of the 7th Annual European Symposium on Algorithms (ESA\u201999), Prague, Czech Republic, 16\u201318 July 1999, Springer.","DOI":"10.1007\/3-540-48481-7_37"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1145\/212332.212334","article-title":"An Empirical Study of Algorithms for Point-Feature Label Placement","volume":"14","author":"Christensen","year":"1995","journal-title":"ACM Trans. Graph."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/s00453-001-0009-7","article-title":"Three Rules Suffice for Good Label Placement","volume":"30","author":"Wagner","year":"2001","journal-title":"Algorithmica"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0925-7721(99)00005-X","article-title":"Point Labeling with Sliding Labels","volume":"13","author":"Strijk","year":"1999","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1023\/A:1015202410664","article-title":"Practical Extensions of Point Labeling in the Slider Model","volume":"6","author":"Strijk","year":"2002","journal-title":"GeoInformatica"},{"key":"ref_23","unstructured":"Meng, Y., Zhang, H., Liu, M., and Liu, S. (2015, January 14\u201317). Clutter-aware label layout. Proceedings of the IEEE Pacific Visualization Symposium (PacificVis 2015), Hangzhou, China."},{"key":"ref_24","unstructured":"Peterson, M.P. (2017). Introducing Leader Lines into Scale-Aware Consistent Labeling. Advances in Cartography and GIScience: Selections from the International Cartographic Conference 2017, Springer International Publishing."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1016\/j.comgeo.2009.03.006","article-title":"Optimizing Active Ranges for Consistent Dynamic Map Labeling","volume":"43","author":"Been","year":"2010","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_26","unstructured":"Raidl, G.R. (1998, January 6\u20139). A Genetic Algorithm for Labeling Point Features. Proceedings of the International Conference on Imaging Science, Systems, and Technology (CISST\u201998), Las Vegas, NV, USA."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2129","DOI":"10.1016\/j.cor.2006.09.024","article-title":"Lagrangean relaxation with clusters for point-feature cartographic label placement problems","volume":"35","author":"Ribeiro","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1023\/A:1013720231747","article-title":"Tabu Search Heuristic for Point-Feature Cartographic Label Placement","volume":"6","author":"Yamamoto","year":"2002","journal-title":"GeoInformatica"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1016\/j.ejor.2007.10.002","article-title":"POPMUSIC for the Point Feature Label Placement Problem","volume":"192","author":"Alvim","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","first-page":"3","article-title":"Optimizing Map Labeling of Point Features Based on an Onion Peeling Approach","volume":"2","author":"Bae","year":"2011","journal-title":"J. Spat. Inf. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"5878","DOI":"10.1016\/j.eswa.2013.04.035","article-title":"Dispersion for the Point-Feature Cartographic Label Placement Problem","volume":"40","author":"Gomes","year":"2013","journal-title":"Expert Syst. Appl."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1111\/gean.12082","article-title":"A Constructive Genetic Algorithm for Discrete Dispersion on Point Feature Cartographic Label Placement Problems","volume":"48","author":"Gomes","year":"2016","journal-title":"Geogr. Anal."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"2164","DOI":"10.1016\/j.cor.2010.03.005","article-title":"A New Mathematical Model and a Lagrangean Decomposition for the Point-Feature Cartographic Label Placement Problem","volume":"37","author":"Mauri","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1016\/j.ejor.2013.10.021","article-title":"A Clustering Search Metaheuristic for the Point-Feature Cartographic Label Placement Problem","volume":"234","author":"Rabello","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1871","DOI":"10.1080\/13658810903401008","article-title":"Area aggregation in map generalisation by mixed-integer programming","volume":"24","author":"Haunert","year":"2010","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1109\/TVCG.2006.136","article-title":"Dynamic Map Labeling","volume":"12","author":"Been","year":"2006","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"De Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, Springer TELOS. [3rd ed.].","DOI":"10.1007\/978-3-540-77974-2"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/11\/342\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:48:15Z","timestamp":1760208495000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/11\/342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,6]]},"references-count":37,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2017,11]]}},"alternative-id":["ijgi6110342"],"URL":"https:\/\/doi.org\/10.3390\/ijgi6110342","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,6]]}}}