Abstract: We propose a novel Inverse Kinematics based deformation method that introduces flexibility and parameterization to motion graphs without degrading the quality of the synthesized motions. Our method deforms the transitions of a motion graph-like structure by first assigning to each transition a continuous rotational range that guarantees not to exceed the predefined global transition cost threshold. The deformation procedure improves the reachability of motion graphs to precise locations and consequently reduces the time spent during search. Furthermore, our method includes a new motion graph construction method based on geometrical segmentation features, and employs a fast triangulation based search pruning technique that confines the search to a free channel and avoids expensive collision checking. The results obtained by the proposed methods were evaluated and quantified, and they demonstrate significant improvements in comparison with traditional motion graph approaches.