After several ad hoc proposals of new 2-dimensional carbon structures, interest in their actual synthesis has begun to increase. One needs a clear orientation or criteria to describe those carbon structures in an appropriate way. In the present paper, we propose a systematic method for discovering new stable structures of carbon crystals with sp2-bonding using advanced mathematical methods. There are two key ideas: geometric descriptions based on curvatures, symmetries, etc. and the standard realization of crystal lattices via harmonic theory to identify stable coordinates. We apply this new method to study negatively curved carbon crystals with octahedral symmetry after Mackay–Terrones , and identify several new structures. The stability and electronic states of the proposed structures are investigated using first principles calculations.