On the expected maximum degree of Gabriel and Yao graphs

Pat Morin

Gabriel graphs (Gabriel and Sokal 1969) and Yao graphs (Yao 1982) are two types of proximity graphs defined on a set of points in the plane. In recent years, these two graphs have found applications in (the theory of) wireless ad hoc networks. Gabriel graphs have been used in the design of guaranteed delivery routing protocols (Bose et al 2001, Karp and Kung 2000) while Yao graphs have been used in the design of power-efficient routing protocols (Li et al. 2001, Bahl et al. 2001). In this talk we define Gabriel graphs and Yao graphs and sketch their applications to wireless networks. We then consider the maximum degree of any vertex in a Gabriel graph or a Yao graph. We show that for points uniformly distributed in a unit square, the maximum degree of any vertex is Theta(log n/log log n) with probability that tends to 1 as n tends to infinity.