Deformable image registration is a field that has received considerable attention in the medical image analysis community. As a consequence, there is an important body of works that aims to tackle deformable registration. In this chapter we review one class of these techniques that use discrete optimization, and more specifically Markov Random Field models. We begin the chapter by explaining how one can formulate the deformable registration problem as a minimal cost graph problem where the nodes of the graph corresponds to the deformation grid, the graph connectivity encodes regularization constraints, and the labels correspond to 3D displacements. We then explain the use of discrete models in intensity-based volumetric registration. In the third section, we detail the use of Gabor-based attribute vectors in the context of discrete deformable registration, demonstrating the versatility of the graph-based models. In the last section of the chapter, the case of landmark-based registration is discussed. We first explain the discrete graphical model behind establishing landmark correspondences, and then continue to show how one can integrate it with the intensity-based model towards creating enhanced models that combine the best of both worlds.