Abstract: We present SegGraph, a new algorithm for loop-closure detection (LCD) for autonomous robots equipped with three-dimensional laser scanners in outdoor scenes such as urban streets. LCD is to check whether the robot has passed a place near where it visited at some point before, and is a key component of a robot’s simultaneous localization and mapping system. Our SegGraph algorithm consists of three steps: 1) partition each of the two input point clouds into point clusters corre-sponding to smooth surfaces, while discarding the ground planes; 2) construct complete weighted graphs from the cluster sets where weights correspond to distances between surface centroids; 3) check if these two graphs contain a sufficiently large common subgraph. The key novelty of SegGraph is that in matching common subgraphs, we mainly compare the distances between corresponding pairs of surface clusters. The rationale is that, due to noise in point cloud data and imperfection of segmentation techniques, different point clouds obtained from nearby places may often be partitioned into drastically different surface segments. However, distances between centroids of these segments tend to be stable across different point clouds. We develope an efficient heuristic randomized algorithm for finding common subgraphs, implement a full LCD algorithm and evaluate it on the publicly available KITTI dataset, which is one of the most widely used. Experimental results demonstrate that our LCD algorithm achieves good accuracy and efficiency.