In the present study, by means of density functional theory (DFT) calculations, the catalytic oxidation of CO by O2 molecule is investigated over Al- and Ge-embedded graphene. The large atomic radius of these dopant atoms can induce a local surface curvature and modulate the electronic structure properties of the graphene sheet through the charge redistribution. It is found that the adsorption of molecular O2 over Al- or Ge-embedded graphene is stronger than that of CO molecule. The CO oxidation reaction by molecular O2 on Al- and Ge-embedded graphene is comparably studied. The results indicate that a two-step process can occur, namely, CO + O2 → CO2 + Oads and CO + Oads → CO2. Furthermore, the computed activation energy (Eact) for the first reaction on Ge-doped graphene is lower than that of Al-doped one, and the formation of second CO2 molecule on both surfaces can occur rapidly due to its low energy barrier (0.1 eV).