Abstract
Map labeling is a classical problem in cartography and geographic information systems (GIS) 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., overlapfree, labels. A practically interesting case is point labeling with axisparallel rectangular labels of common size. In a fully dynamic setting, at each time step, 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 (MIS) and maximum independent set (MaxIS) problems on fully dynamic (insertion/deletion model) sets of axisparallel 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.
We present the first deterministic algorithm for maintaining a MIS (and thus a 4approximate MaxIS) of a dynamic set of uniform rectangles with amortized sublogarithmic update time. This breaks the natural barrier of Ω(Δ) update time (where Δ is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating MaxIS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4approximate MaxIS with O(1) update time. In a subsequent algorithm, we establish the tradeoff between approximation quality 2(1+1/k) and update time O(k²log n), for k ∈ ℕ. We conclude with an algorithm that maintains a 2approximate MaxIS for dynamic sets of unitheight and arbitrarywidth rectangles with O(ω log n) update time, where ω is the maximum size of an independent set of rectangles stabbed by any horizontal line. We have implemented our algorithms and report the results of an experimental comparison exploring the tradeoff between solution quality and update time for synthetic and realworld map labeling instances.
BibTeX  Entry
@InProceedings{bhore_et_al:LIPIcs:2020:12885,
author = {Sujoy Bhore and Guangping Li and Martin N{\"o}llenburg},
title = {{An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {19:119:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12885},
URN = {urn:nbn:de:0030drops128856},
doi = {10.4230/LIPIcs.ESA.2020.19},
annote = {Keywords: Independent Sets, Dynamic Algorithms, Rectangle Intersection Graphs, Approximation Algorithms, Experimental Evaluation}
}
Keywords: 

Independent Sets, Dynamic Algorithms, Rectangle Intersection Graphs, Approximation Algorithms, Experimental Evaluation 
Collection: 

28th Annual European Symposium on Algorithms (ESA 2020) 
Issue Date: 

2020 
Date of publication: 

26.08.2020 
Supplementary Material: 

Source code and benchmark data at https://dynamis.github.io/dynaMIS/. 