  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.,
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 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 sub-linear update time. Motivated by this, we study the
maximal independent set ((MIS)) and maximum independent set (Max-IS) 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.
  We present the first deterministic algorithm for maintaining an MIS (and thus
a 4-approximate Max-IS) of a dynamic set of uniform rectangles with
polylogarithmic update time. This breaks the natural barrier of
$\Omega(\Delta)$ update time (where $\Delta$ is the maximum degree in the
graph) for \emph{vertex updates} presented by Assadi et al. (STOC 2018). We
continue by investigating Max-IS and provide a series of deterministic dynamic
approximation schemes with approximation factors between 2 and 4 and
corresponding running-time trade-offs. We have implemented our algorithms and
reported the results of an experimental comparison exploring the trade-off
between solution quality and update time for synthetic and real-world map
labeling instances.
