The separation of water and fat from multi-echo images is a classic problem in magnetic resonance imaging (MRI) with a wide range of important clinical applications. For example, removal of fat signal can provide better visualization of other signal of interest in MRI scans. In other cases, the fat distribution map can be of great importance in diagnosis. Although many methods have been proposed over the past three decades, robust fat water separation remains a challenge as radiological technology and clinical expectation continue to grow. The problem presents three key difficulties: a) the presence of B0 field inhomogeneities, often large in the state-of-the-art research and clinical settings, which makes the problem non-linear and ill-posed; b) the ambiguity of signal modeling in locations with only one metabolite (either fat or water), which can manifest as spurious fat water swaps in the separation; c) the computational expenditure in fat water separation as the size of the data is increasing along with evolving MRI hardware, which hampers the clinical applicability of the fat water separation. The main focus of this thesis is to develop novel graph based algorithms to estimate the B0 field inhomogeneity maps and separate fat water signals with global accuracy and computational efficiency. We propose a new smoothness constrained framework for the GlObally Optimal Surface Estimation (GOOSE), in which the spatial smoothness of the B0 field is modeled as a finite constraint between adjacent voxels in a uniformly discretized graph. We further develop a new non-equidistant graph model that enables a Rapid GlObally Optimal Surface Estimation (R-GOOSE) in a subset of the fully discretized graph in GOOSE. Extensions of the above frameworks are also developed to achieve high computational efficiency for processing large 3D datasets. Global convergence of the optimization formulation is proven in all frameworks. The developed methods have also been extensively compared to the existing state-of-the-art fat water separation methods on a variety of datasets with consistent performance of high accuracy and efficiency.