Purpose: This paper introduces a novel decomposed graphical model to deal with slice-to-volume registration in the context of medical images and image guided surgeries. Methods: We present a new non-rigid slice-to-volume registration method whose main contribution is the ability to decouple the plane selection and the in-plane deformation parts of the transformation -through two distinct graphs- towards reducing the complexity of the model while being able to obtain simultaneously the solution for both of them. To this end, the plane selection process is expressed as a local graph-labeling problem endowed with planarity satisfaction constraints, which is then directly linked with the deformable part through the data registration likelihoods. The resulting model is modular with respect to the image metric, can cope with arbitrary in-plane regularization terms and inherits excellent properties in terms of computational efficiency. Results: The proof of concept for the proposed formulation is done using cardiac MR sequences of a beating heart (an artificially generated 2D temporal sequence is extracted using real data with known ground truth) as well as multimodal brain images involving ultrasound and computed tomography images. We achieve state of the art results while decreasing the computational time when we compare with another method based on similar techniques. Conclusions: We confirm that graphical models and discrete optimization techniques are suitable to solve non-rigid slice-to-volume registration problems. Moreover, we show that decoupling the graphical model and labeling it using two lower dimensional label spaces, we can achieve state of the art results while substantially reducing the complexity of our method and moving the approach close to real clinical applications once considered in the context of modern parallel architectures.