A random geometric graph (https://en.wikipedia.org/wiki/Random_geometric_graph) is constructed by choosing $n$ points in $\mathbb{R}^d$ at random according to some distribution, and setting $p_i \sim p_j$ if $\|p_i - p_j\|<r$, for some parameter $r$. Geometric graphs are of use in modelling real world networks.

For example, we can model a transportation map using the uniform distribution on $[0,1]^2$.

I am interested in whether there are good graph theoretic algorithms for dealing with these graphs. For example, is there an algorithm for finding the shortest path between two vertices that is better (in expectation) for these graphs than BFS? Obviously such an algorithm would be useful for GPS manufacturers.

Does research like this exist?


1 Answer 1


The graphs that you get are known as unit disk graphs. There is a vast literature about algorithms on unit disk graphs. Since you are asking about shortest paths, check out this article by Cabello and Jejcic. Of course all of this will not take into account that the graphs are generated by some random process.

For further references consult the wikipedia page or the Cabello and Jejcic paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.