Editing Independent set (graph theory) (section)

==== In geometric intersection graphs ====
{{Main|Maximum disjoint set}}
A geometric [[intersection graph]] is a graph in which the nodes are geometric shapes and there is an edge between two shapes if and only if they intersect. An independent set in a geometric intersection graph is just a set of disjoint (non-overlapping) shapes. The problem of finding maximum independent sets in geometric intersection graphs has been studied, for example, in the context of [[Automatic label placement]]: given a set of locations in a map, find a maximum set of disjoint rectangular labels near these locations.

Finding a maximum independent set in intersection graphs is still NP-complete, but it is easier to approximate than the general maximum independent set problem. A recent survey can be found in the introduction of {{harvtxt|Chan|Har-Peled|2012}}.