This paper provides theoretical foundation for the problem of localization in multi-robot formations. Sufficient and necessary conditions for completely localizing a formation of mobile robots/vehicles in SE(2) based on distributed sensor networks and graph rigidity are proposed. A method for estimating the quality of localizations via a linearized weighted least-squares algorithm is presented, which considers incomplete and noisy sensory information. The approach in this paper had been implemented in a multi-robot system of five car-like robots equipped with omni-directional cameras and IEEE 802.11b wireless network.