PROXIMITY STRUCTURES FOR GEOMETRIC GRAPHS.

In this paper we study proximity graph structures like Delaunay triangulations based on geometric graphs, i.e. graphs which are subgraphs of the complete geometric graph. Given an arbitrary geometric graph G, we define Voronoi diagrams, Delaunay triangulations, relative neighborhood graphs, Gabriel graphs which are related to the graph structure and then study their complexities when G is a general geometric graph or G is some special graph derived from the application area of wireless networks. Besides being of fundamental interest these structures have applications in topology control for wireless networks. [ABSTRACT FROM AUTHOR]