To gain qualitative and quantitative understanding of oxidation processes of large polycyclic aromatics, soot particles, and graphene edges, a theoretical study is reported for the pyrenyl-O2 reaction system. First, possible reaction pathways and their energetics were investigated using high-level ab initio calculations. The results were utilized in RRKM-master equation calculations of rate coefficients and relative product yields at temperatures and pressures relevant to combustion. Finally, the deduced oxidation mechanisms of six- and five-member rings and the computed rate coefficients were employed in kinetic Monte Carlo simulations of oxidation of a graphene "molecule" evolving in flame-like environments. Among the major findings from the latter simulations are the following: The oxidation system exhibits two basic pathways, thermal decomposition and regeneration of oxyradicals. Their competition is temperature-dependent, with the former dominating at higher and the latter at lower temperatures. The overall oxidation of the graphene substrate is computed to be time-dependent, with the initial rates consistent with the known experimental data.