2019

# Plane and planarity thresholds for random geometric graphs

## Publication

### Publication

*
Discrete Mathematics, Algorithms and Applications
*

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.

Additional Metadata | |
---|---|

distance threshold, planar graph, plane graph, Random geometric graph | |

dx.doi.org/10.1142/S1793830920500056 | |

Discrete Mathematics, Algorithms and Applications | |

Organisation | 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 |