Menu
For constructing routes in mobile ad-hoc networks (MANET) and sensor networks, it is highly desirable to perform primitive computations locally. If a network can be represented in the doubly connected edge list (DCEL) data structure, then many operations can be done locally. However, the DCEL data structure can be used to represent only planar graphs. In this paper, we propose an extended version of the DCEL data structure called ExtDCEL that can be used for representing non-planar graphs as well as their planar components. The proposed data structure can be used to represent geometric networks in mobile computing that include unit disk graphs, Gabriel graphs, and constrained Delaunay triangulations. We show how the proposed data structure can be used to implement a hybrid greedy face routing algorithm in optimum \( O(m) \) time, where \( m \) is the number of edges in the unit disk graph. We also report on the implementation of several routing algorithms for mobile computing by using the proposed data structure.