In this paper we propose a novel graph-based concurrent registration and segmentation framework. Registration is modeled with a pairwise graphical model formulation that is modular with respect to the data and regularization term. Segmentation is addressed by adopt- ing a similar graphical model, using image-based classi cation techniques while producing a smooth solution. The two problems are coupled via a relaxation of the registration criterion in the presence of tumors as well as a segmentation through a registration term aiming the separation be- tween healthy and diseased tissues. E cient linear programming is used to solve both problems simultaneously. State of the art results demon- strate the potential of our method on a large and challenging low-grade glioma data set.