Image segmentation plays vital role in computer vision for image retrieval, visual summary, image base modeling, and for many other purposes. Despite many years of research and significant contributions, image segmentation is still a very challenging task to suit for variety of applications. Among the different segmentation approaches, graph theoretical approach is the most popular since it has capabilities of organizing the image elements into accurate mathematical structures and makes the formulation computationally efficient This paper critically reviews recent graph based segmentation methods along with their detailed analysis, experimental performance and evaluation on the basis of Berkeley benchmark The study and evaluation is useful in improving the performance of existing methods as well as helpful in the development of new methods. © 2014 IEEE.