A random geometric graph, G(n,r), is formed by choosing n points independently and uniformly at random in a unit square; two points are connected by a straight-line edge if they are at Euclidean distance at most r. For a given constant k, we show that n -k 2k-2 is a distance threshold function for G(n,r) to have a connected subgraph on k points. Based on this, we show that n-2/3 is a distance threshold for G(n,r) to be plane, and n-5/8 is a distance threshold to be planar. We also investigate distance thresholds for G(n,r) to have a non-crossing edge, a clique of a given size, and an independent set of a given size.

, , ,
Discrete Mathematics, Algorithms and Applications
Computational Geometry Lab

Biniaz, A. (Ahmad), Kranakis, E, Maheshwari, A, & Smid, M. (2019). Plane and planarity thresholds for random geometric graphs. Discrete Mathematics, Algorithms and Applications. doi:10.1142/S1793830920500056