{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T01:53:13Z","timestamp":1772502793608,"version":"3.50.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T00:00:00Z","timestamp":1657152000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"\n Map labeling is a classical problem in cartography and geographic information systems that asks to place labels for area, line, and point features, with the goal to select and place the maximum number of independent (i.e., overlap-free) labels. A practically interesting case is point labeling with axis-parallel rectangular labels of common size. In a fully dynamic setting, at each timestep, either a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum cardinality subset of pairwise independent labels with sublinear update time. Motivated by this, we study the maximal independent set (\n MIS<\/jats:sc>\n ) and maximum independent set (\n Max-IS<\/jats:sc>\n ) problems on fully dynamic (insertion\/deletion model) sets of axis-parallel rectangles of two types: (i) uniform height and width and (ii) uniform height and arbitrary width; both settings can be modeled as rectangle intersection graphs.\n <\/jats:p>\n \n \u00a0\u00a0 We present the first deterministic algorithm for maintaining an\n MIS<\/jats:sc>\n (and thus a 4-approximate\n Max-IS<\/jats:sc>\n ) of a dynamic set of uniform rectangles with polylogarithmic update time. This breaks the natural barrier of\n \n \\( \\Omega (\\Delta) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n update time (where\n \n \\( \\Delta \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the maximum degree in the graph) for\n vertex updates<\/jats:italic>\n presented by Assadi et\u00a0al.\u00a0(STOC 2018). We continue by investigating\n Max-IS<\/jats:sc>\n and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4-approximate\n Max-IS<\/jats:sc>\n with\n \n \\( O(1) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n update time. In a subsequent algorithm, we establish the trade-off between approximation quality\n \n \\( 2(1+\\frac{1}{k}) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and update time\n \n \\( O(k^2\\log n) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , for\n \n \\( k\\in \\mathbb {N} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We conclude with an algorithm that maintains a 2-approximate\n Max-IS<\/jats:sc>\n for dynamic sets of unit-height and arbitrary-width rectangles with\n \n \\( O(\\log ^2 n + \\omega \\log n) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n update time, where\n \n \\( \\omega \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the maximum size of an independent set of rectangles stabbed by any horizontal line. We implement our algorithms and report the results of an experimental comparison exploring the trade-off between solution quality and update time for synthetic and real-world map labeling instances. We made several major observations in our empirical study. First, the original approximations are well above their respective worst-case ratios. Second, in comparison with the static approaches, the dynamic approaches show a significant speedup in practice. Third, the approximation algorithms show their predicted relative behavior. The better the solution quality, the worse the update times. Fourth, a simple greedy augmentation to the approximate solutions of the algorithms boost the solution sizes significantly in practice.\n <\/jats:p>","DOI":"10.1145\/3514240","type":"journal-article","created":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T12:05:12Z","timestamp":1657195512000},"page":"1-36","source":"Crossref","is-referenced-by-count":2,"title":["An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0104-1659","authenticated-orcid":false,"given":"Sujoy","family":"Bhore","sequence":"first","affiliation":[{"name":"Indian Institute of Science Education and Research, Bhopal, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7966-076X","authenticated-orcid":false,"given":"Guangping","family":"Li","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-3937","authenticated-orcid":false,"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,7]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316376"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.50"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00028-5"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.116"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.136"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.03.006"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00032"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.115"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.1"},{"key":"e_1_3_2_12_2","article-title":"Dynamic geometric independent set","volume":"2007","author":"Bhore Sujoy","year":"2020","unstructured":"Sujoy Bhore, Jean Cardinal, John Iacono, and Grigorios Koumoutsos. 2020. Dynamic geometric independent set. CoRR abs\/2007.08643 (2020). https:\/\/arxiv.org\/abs\/2007.08643.","journal-title":"CoRR"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.97"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9417-5"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2017.28"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00031"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/212332.212334"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.92"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.45"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_32"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvlc.2006.03.004"},{"key":"e_1_3_2_22_2","volume-title":"Algorithms and Theory of Computation Handbook","author":"Eppstein David","year":"1999","unstructured":"David Eppstein, Zvi Galil, and Giuseppe F. Italiano. 1999. Dynamic graph algorithms. In Algorithms and Theory of Computation Handbook, Mikhail J. Atallah (Ed.). CRC Press, Boca Raton, FL, 1\u201328."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539702402676"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/109648.109680"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23519-6_1646-1"},{"key":"e_1_3_2_27_2","volume":"2106","author":"G\u00e1lvez Waldo","year":"2021","unstructured":"Waldo G\u00e1lvez, Arindam Khan, Mathieu Mari, Tobias M\u00f6mke, Madhusudhan Reddy Pittu, and Andreas Wiese. 2021. A 3-Approximation Algorithm for Maximum Independent Set of Rectangles. CoRR abs\/2106.00623 (2021). https:\/\/dblp.org\/rec\/conf\/soda\/GalvezKMMPW22.html?view=bibtex.","journal-title":"CoRR"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00011"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.09.046"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2851493"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v7i1a15"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120410"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2020.51"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359359"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/VAST.2011.6102456"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840386"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/204865.204889"},{"key":"e_1_3_2_42_2","article-title":"Approximating maximum independent set for rectangles in the plane","volume":"2101","author":"Mitchell Joseph S. B.","year":"2021","unstructured":"Joseph S. B. Mitchell. 2021. Approximating maximum independent set for rectangles in the plane. CoRR abs\/2101.00326 (2021). https:\/\/arxiv.org\/abs\/2101.00326.","journal-title":"CoRR"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.81"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01098364"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.3138\/carto.49.1.2137"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409097"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/PacificVis.2012.6183572"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-014-0398-5"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276922"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00007-7"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3839"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514240","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:14Z","timestamp":1750183814000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,7]]},"references-count":51,"alternative-id":["10.1145\/3514240"],"URL":"https:\/\/doi.org\/10.1145\/3514240","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,7]]}}}