We present a Graph-based method for low-level segmentation of unfiltered 3D data. The core of this approach is based on the construction of a local neighborhood structure and its recursive subdivision. The Minimum Spanning Tree (MST) is the graph support used to measure the attribute variation through the region. The subdivision criterion relies on the evidence for a boundary between two partitions, which is detected through MST edge analysis. Although our algorithm converges to a local minimum, our experiments show that it produces segments that satisfy global properties. We assume that the 3D image is composed of regions homogeneous according to some criterion (color, curvature, etc.), but no assumption about noise, nor spatial repartition/shape of the regions or points is made. Robustness is achieved by choosing the appropriate neighborhood and the analysis of noise impact on the MST construction. We demonstrate the performance of our algorithm with experimental results on real images.