On Locally Gabriel Geometric Graphs

Let P be a set of n points in the plane. A geometric graph G on P is said to be locally gabriel if for every edge (u, v) in G, the disc with u and v as diameter does not contain any points of P that are neighbors of u or v in G. Motivated by applications in topol-ogy control of wireless networks, [KL03] initiated the study of this graph. An interesting combinatorial question is to bound the edge complexity of locally gabriel graphs. We show the following results: (i) For any n, there exists locally gabriel graphs with Ω(n5/4) edges. This improves upon the previous best bound of Ω(n1+ c log log n). (ii) For points in convex position, we show that any locally gabriel graph has O(n log n) edges.