Random Geometric Graphs and Their Applications

Project: Research

View graph of relations

Researcher(s)

Description

A random geometric graph (with parametersn, r) is constructed by first scatteringnpoints randomly and uniformly into the unit square (or more generally according to some specific density function inEd) and then adding edges to connect any two points that are within distancerfrom each other. This definition provides a more realistic model compared with the classical random graphs of Erdös and Rényi, especially for applications in wireless sensor networks, epidemiology, astronomy, geology, and so on. In this project, the researchers plan to study various topological and communications properties of random geometric graphs motivated by applications in wireless sensor networks:the length of the longest edge of various geometric spanners such as the relative neighbour graph, localized minimum spanning trees, the Yao graph, and localized Delaunay triangulations;the longest edge of the minimum spanning tree with randomized key pre-distribution; andthe maximum degree, minimum degree, clique number, and chromatic number of the square of random geometric graphs.The researchers propose to derive tight a.a.s. (asymptotically almost sure) bounds as well as determine the asymptotic distributions of these important topological parameters.

Detail(s)

Project number9041270
Grant typeGRF
StatusFinished
Effective start/end date1/01/082/03/11