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 (Formula presented.) is a distance threshold function for G(n, r) to have a connected subgraph on k points. Based on that, we show that n− 2/3 is a distance threshold function for G(n, r) to be plane, and n− 5/8 is a distance threshold function for G(n, r) to be planar.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-319-28472-9_1
Citation
Biniaz, A. (Ahmad), Kranakis, E, Maheshwari, A, & Smid, M. (2015). Plane and planarity thresholds for random geometric graphs. doi:10.1007/978-3-319-28472-9_1