A graph-based segmentation technique has been tailored to segment airborne LiDAR points which, unlike images, are irregularly distributed. In our method, every LiDAR point is labeled as a node and interconnected as a graph extended to its neighborhood, defined in a 4-D feature space: the spatial coordinates () and the reflection intensity. The interconnections between pairs of neighboring nodes are weighted based on the distance in the feature space. The segmentation consists of an iterative process of classification of nodes into homogeneous groups based on their similarity. This approach is intended to be part of a complete system for the classification of structures from LiDAR point clouds in applications needing fast response times. In this sense, a study of the performance/accuracy trade-off has been performed, extracting some conclusions about the benefits of the proposed solution. In addition, an interlaced graph-based approach is proposed to increase the reliability in general purpose segmentations.