Geographic Perimeter Stateless Routing (GPSR) makes use of location information to forward packets greedily. Nodes need to keep only this local information, hence called as stateless. There are two graphs used for the planarization namely the Gabriel Graph (GG) and the Relative Neighbourhood Graph (RNG) but they were very expensive and had to be run for each node whenever greedy forwarding failed. So it was further replaced by CLDP, however it also suffered from drawbacks both in terms of cost and complications. Here, we propose a cost-effective scheme which makes use of k-hop neighbourhood knowledge and this heuristic is applied when greedy forwarding fails and is used instead of face routing and planarization. Moreover it proves to be better than planarization in most of the cases. © 2013 IEEE.