Independent set of intersection graphs of convex objects in 2D

https://doi.org/10.1016/j.comgeo.2005.12.001Get rights and content
Under an Elsevier user license
open archive

Abstract

The intersection graph of a set of geometric objects is defined as a graph G=(S,E) in which there is an edge between two nodes si, sjS if sisj. The problem of computing a maximum independent set in the intersection graph of a set of objects is known to be NP-complete for most cases in two and higher dimensions. We present approximation algorithms for computing a maximum independent set of intersection graphs of convex objects in R2. Specifically, given (i) a set of n line segments in the plane with maximum independent set of size α, we present algorithms that find an independent set of size at least (α/(2log(2n/α)))1/2 in time O(n3) and (α/(2log(2n/α)))1/4 in time O(n4/3logcn), (ii) a set of n convex objects with maximum independent set of size α, we present an algorithm that finds an independent set of size at least (α/(2log(2n/α)))1/3 in time O(n3+τ(S)), assuming that S can be preprocessed in time τ(S) to answer certain primitive operations on these convex sets, and (iii) a set of n rectangles with maximum independent set of size βn, for β1, we present an algorithm that computes an independent set of size Ω(β2n). All our algorithms use the notion of partial orders that exploit the geometric structure of the convex objects.

Keywords

Approximation algorithms
Maximum independent set
Geometric intersection graphs
Convex objects

Cited by (0)

Research is supported by NSF grants ITR-333-1050, EIA-98-70724, EIA-01-31905, and CCR-00-86013.