This paper addresses false data injection, which is one of the most significant security challenges in smart grids. Having an accurately estimated state is of great importance for maintaining a stable running condition of smart grids. To preserve the accuracy of the estimated state, bad data detection (BDD) mechanisms are utilized to remove erroneous measurements due to meter failures or outsider attacks. In this paper we use a graph-theoretical formulation for false data injection attacks in smart grids and propose defense mechanisms to mitigating this type of attacks. To this end we discuss characteristics of a typical smart grid graph such as planarity. Then we propose three different approaches for finding optimal protected meters set: a fast and efficient heuristic algorithm that works well in practice, an approximation algorithm that provides guarantee for the quality of the protected set, and an exact algorithm that find the optimal solution. Our extensive simulation results show that our algorithms outperform similar existing solutions in terms of different performance metrics.