# Transfer-Efficient Face Routing Using the Planar Graphs of Neighbors in High Density WSNs
## 4 Transfer-Efficient Face Routing
### Build a Local Planar Graph  
The second step of TEFR is to construct a local planar graph using the location information on the neighboring nodes and to transfer the information on the constructed planar graph to the message transfer node. The message transfer node and its neighbors generate their own local network graphs and their local GGs are built after planarization. Table 1 shows the edge list of the constructed local network graph of the message transfer node and its neighbors after exchanging location information between nodes in the network in Figure 3. Although the local network graph is part of the overall network graph, it is still possible to cause a loop across the entire network. Thus, even though the local network is tiny, it is necessary to remove any intersecting edges that might cause a loop by applying planarization. A local GG edge list is built for the message transfer node and its neighbors by removing edges that do not satisfy the GG edge condition from the edge list of the local network graphs to prevent looping. Figure 4 shows a local network graph and a local planar graph of node \(i_{6}\) as an example of a planar graph built for the neighbors of a message transfer node. In Figure 4a, to perform planarization for node \(i_{6}\), the GG edge condition is applied to all the edges connected to its neighbors. The resulting planar graph is shown in Figure 4b. Planarization is performed independently on the message transfer node and all its neighbors. The pseudo-code running on each node for generating the GG edge list from the edge list of a local network graph is as follows. ```
\(LNG\): edge list of the local network graph \(LGG\): edge list of the local Gabriel graph for all edges in \(LNG\)do if(there exists no node in the circle with edge's diameter) then  add edge to \(LGG\) endif endfor
```  
**Algorithm 1** Generating the GG edge list from the edge list of a local network graph. Figure 3: Beaconing: the exchange of position information between nodes. The algorithm generates the GG edge list by selecting those edges meeting the GG edge condition among all edges on the local network graph. Table 2 shows the GG edge lists constructed by applying Algorithm 1 to the local network graph edge lists in Table 1. The strikethroughs in Table 2 represent edges that were deleted during planarization, so are not GG edges. Since TEFR distributes planarization to the message transfer nodes' neighbors, it is possible to solve the problem that the load is concentrated on the message transfer nodes, which makes face routing using 2-hop node information so inefficient. Moreover, because the message transfer node only receives information of the planar graph nodes rather than of all neighboring nodes, the amount of position information to be transmitted can be reduced. In addition, the changes are transmitted to the message transfer node each time a node is added or removed only if the planar graph is affected due to a change in topology. topology is changed but the changes do not affect the planar graph, while Figure 6 shows the opposite case to Figure 5 where the changed node information should be sent to the message transfer node. Figure 5a is the local network where new nodes \(a_{1}\) and \(a_{2}\) are added, and node \(i_{3}\) is deleted in the network of Figure 4a. Even if nodes \(a_{1}\) and \(a_{2}\) are added but the edges between node \(i_{6}\) and them are deleted during planarization, this does not affect the existing planar graph. Furthermore, even though node \(i_{3}\) is removed from the network since \(edge(i_{6},i_{3})\) has already been deleted from the existing planar graph due to not fitting the GG edge condition, this also does not affect the existing planar graph. Figure 5b shows the planar graph after topological changes have occurred. Since it is the same as before the network change, the changed node information is not transmitted even though there have been topological changes. Figure 6 shows the case where a topological change affects the planar graph.