Image segmentation plays a crucial role in effective understanding of digital images. Past few decades saw hundreds of research contributions in this field. However, the research on the existence of general purpose segmentation algorithm that suits for variety of applications is still very much active. Among the many approaches in performing image segmentation, graph based approach is gaining popularity primarily due to its ability in reflecting global image properties. This paper critically reviews existing important graph based segmentation methods. The review is done based on the classification of various segmentation algorithms within the framework of graph based approaches. The major four categorizations we have employed for the purpose of review are: graph cut based methods, interactive methods, minimum spanning tree based methods and pyramid based methods. This review not only reveals the pros in each method and category but also explores its limitations. In addition, the review highlights the need for creating a database for benchmarking intensity based algorithms, and the need for further research in graph based segmentation for automated real time applications.