Extracting planar surfaces from 3D point clouds is an important and challenging step for generating building models as the obtained data are always noisy, missing and unorganised. In this paper, we present a novel graph Laplacian regularized K-planes method for segmenting piece-wise planar surfaces of urban building point clouds. The core ideas behind our model are from two aspects: 1) a linear projection model is utilized to fit planar surfaces globally; 2) a graph Laplacian regularization is applied to preserve smoothness of each plane locally. The two terms are combined as an objective function, which is minimized via an iterative updating algorithm. Comparative experiments on both synthetic and real data sets are performed. The results demonstrate the effectiveness and efficiency of our method.