Image retargeting techniques aim to adapt images to the target screens with different sizes and aspect ratios. Unfortunately, image retargeting for mobile device screens suffers from the problems of limited display area and various aspect ratios. This has been one of the hot topics in multimedia research. This paper proposes a novel image retargeting approach based on region relation graph. First, energy map and sensitivity energy maps are calculated by visual attention and weighted gradient, respectively. Then, the original image is decomposed into curve-edge trapezoid meshes, further represented by region relation graph. Based on the region relation graph, image retargeting is formulated as a quadratic programming problem constrained by energy maps, which emphasizes the important image parts and reduces the visual distortion by optimally relocating the key mesh vertexes. Finally, the target image is generated based on the optimal solution. Experimental results show the effective and efficiency of the proposed approach.