Planar reconstruction patterns at the zigzag and armchair edges of graphene were investigated with density-functional theory. It was unexpectedly found that the zigzag edge is metastable and a planar reconstruction spontaneously takes place at room temperature. The reconstruction changes electronic structure and self-passivates the edge with respect to adsorption of atomic hydrogen from a molecular atmosphere.