Geographic Perimeter Stateless Routing (GPSR) use local information to forward packets greedily. Nodes need to keep only this information, hence called as stateless. When not possible the algorithm and Greedy forwarding recovers to this scenario by switching to face routing, which is further based on the right-hand rule in the planarized node graph, in order to route around the void. The Gabriel Graph(GG) and the Relative Neighbourhood Graph (RNG) are the two graphs used for the planarization, but results in graph partitioning. In this work, we propose an improvised RNG-GG algorithm which makes sure to avoid the partitioning of the underlying connected graph and the cross-link, which remain in the node connectivity graph. We have given simulation results for the performance analysis of our proposed protocol compared to the competitive schemes and found improvement in terms of an increased packet delivery success rate, reducing routing protocol overhead and increased the path length. © 2013 IEEE.