We present a new approach to the stereo-matching problem. Images are individually described by aneighborhood graph of line segments coming from a polygonal approximation of the contours. The matching process is defined as the exploration of the largest components of adisparity graph built from the descriptions of the two images, and is performed by an efficient prediction and propagation technique. This approach was tested on a variety of man-made environments, and it appears to be fast and robust enough for mobile robot navigation and three-dimensional part-positioning applications.