We formulated a sparse map representation using an embedded labeled directed graph structure that compactly represents geometry as well as occlusions and frontier information. We tailored the particle filter framework to accommodate this map structure so each robot can incrementally updated and correct errors in its map. Finally, we developed a distributed algorithm to guide the exploration of the environment and enable the robots to verify shared information before it is accepted.