Reasoning about three-dimensional scenes involves the analysis of large amounts of complex, time-varying information. This paper presents a novel representation for storing such information that provides a unified, intuitive framework for reasoning about rigid objects. The core structure is a graph that represents features of the scene as vertices, and stores distances between these features at the edges. These relation- ships evolve over time, as more information is presented to the system, and an ap- proach to dealing with uncertain information using interval arithmetic is proposed. An algorithm for rigid object extraction is presented, based on this graph. The graph structure can also be used in support of some low-level tasks, and the problem of track- ing three-dimensional features is considered. Results are presented for both artificial and real scenes.