The spin-dependent electronic structure of graphene is investigated by first-principles calculations, using relativistic full-potential linearized augmented plane wave and Korringa-Kohn-Rostoker methods. Our systematic study addresses various effects on the electronic states at the Dirac points: in-plane and out-of-plane deformation of graphene's honeycomb lattice, external electric fields, doping and band filling due to heavy and magnetic adatoms (Au and Ni). Having revealed the underlying mechanisms, our findings open a route to manufacture graphene with sizable spin splittings.