Independent set of intersection graphs of convex objects in 2D
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, sj ∈ S if si ∩ sj ≠ ∅. 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 ℝ2. Specifically, given 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 (i) (κ/2 log(2n/κ))1/2 in time O(n3) and (ii) (κ/2 log(2n/κ))1/4 in time O(n4/3 logc n). For 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 (κ/2 log(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. © Springer-Verlag Berlin Heidelberg 2004.
Volume / Issue
Start / End Page
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)