On the Expected Maximum Degree of Gabriel and Yao Graphs

Abstract

Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximal degree of a random Gabriel graph or Yao graph defined on $n$ points drawn uniformly at random from a unit square grows as $\Theta (\log n/\log \log n)$ in probability.

20 pages, 10 figures