I was wondering if a lot is known about independent sets in Random Geometric graphs? Most google searches don't bring up much. In addition I'm interested in any algorithms used for finding independent sets in Random Geometric Graphs.
Unit disk graphs are a special type of random geometric graphs, where two of the given nodes on a plane share an edge if their Euclidean distance is less or equal to one. This class has been studied quite a lot and it is probably a good starting point for you. I'm not an expert, but here is a list of paper (and references therein) where I would start from (in chronological order).
- B. N. Clark, C. J. Colbourn, D. S. Johnson, Unit disk graphs (1990)
- J. Díaz, J. Petit, M. Serna, Random Geometric Problems on $[0, 1]^2$ (1999)
- T. Nieberg, J. Hurink, W. Kern, A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs (2005)
- W. Wua, H. Dub, X. Jiab, Y. Lic, S. C.H. Huangb, Minimum connected dominating sets and maximal independent sets in unit disk graphs (2006)
- C. Mcdiarmid, T. Müller, On the chromatic number of random geometric graphs (2011)
- D. Mahjoub, D. W. Matula, Experimental Study of Independent and Dominating Sets in Wireless Sensor Networks Using Graph Coloring Algorithms (2009)
- P. Hu, K. Xing, L. Huang, Y. Wang, D. Wang, P. Li, A Maximal Independent Set Based Giant Component Formation in Random Unit-Disk Graphs (2011)