 We study the maximal independent set (MIS) and maximum independent set ( MAX-IS ) problems on dynamic sets of O(n) axis-parallel rectangles, which can be modeled as dynamic rectangle intersection graphs. We consider the fully dynamic vertex update (insertion/deletion ) modelfor two types of rectangles: (i) uniform height and width and (ii) uniform height and arbitrary width . These types of dynamic vertex update problems arise, e.g., in interactive map labeling. We present the first deterministic algorithm for maintaining a MIS (and thus a 4-approximate MAX-IS ) of a dynamic set of uniform rectangles with amortized sub-logarithmic update time. This breaks the natural barrier of O (\Delta) update time (where \Delta is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating MAX-IS and provide a series of deterministic dynamic approximation schemes . For uniform rectangles, we first give an algorithm that maintains a 4-approximate MAX-IS with O(1) update time. In a subsequent algorithm, we establish the trade-off between approximation quality 2 (1+\frac{1{k}) and update time O(k^2\log n) for k\in \mathbb{N}. We conclude with an algorithm that maintains a 2-approximate MAX-IS for dynamic sets of uniform height and arbitrary width rectangles with O(\omega \log n) update time, where \omega is the largest number of maximal cliques stabbed by any axis-parallel line}  . We have implemented our algorithms and report the results of an experimental comparison exploring the trade-off between solution size and update time for synthetic and real-world map labeling data sets .
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 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. 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 a MIS (and thus a 4-approximate Max-IS ) of a dynamic set of uniform rectangles with amortized sub-logarithmic update time. This breaks the natural barrier of \Omega (\Delta) update time (where \Delta is the maximum degree in the graph) for 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 {k}) and update time O(k^2\log n) for k\in \mathbb{N}. We conclude with an algorithm that maintains a 2-approximate MAX-IS for dynamic sets of uniform height and arbitrary width rectangles with O(\omega \log n) update time, where \omega is the largest number of maximal cliques stabbed by any axis-parallel line} and 4 and corresponding running-time trade-offs . We have implemented 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 .
A
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 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.
R
MAX-IS
Max-IS
R
dynamic sets of O(n) axis-parallel rectangles, which can be modeled as dynamic rectangle intersection graphs. We consider the fully dynamic vertex update
fully dynamic
R
) modelfor two types of rectangles:
model) sets of axis-parallel rectangles of two types---
R
. These types of dynamic vertex update problems arise, e.g., in interactive map labeling.
; both settings can be modeled as rectangle intersection graphs.
R
MAX-IS
Max-IS
R
O
\Omega
R
MAX-IS
Max-IS
R
. For uniform rectangles, we first give an algorithm that maintains a 4-approximate MAX-IS with O(1) update time. In a subsequent algorithm, we establish the trade-off between approximation quality
with approximation factors between
D
(1+\frac{1
A
and 4 and corresponding running-time trade-offs
R
size
quality
R
data sets
instances