Methods of forming a graphene-based device are provided. According to an embodiment, a graphene-based device can be formed by subjecting a substrate having a dielectric formed thereon to a chemical vapor deposition (CVD) process using a cracked hydrocarbon or a physical vapor deposition (PVD) process using a graphite source; and performing an annealing process. The annealing process can be performed to temperatures of 1000 K or more. The cracked hydrocarbon of the CVD process can be cracked ethylene. In accordance with one embodiment, the application of the cracked ethylene to a MgO(111) surface followed by an annealing under ultra high vacuum conditions can result in a structure on the MgO(111) surface of an ordered graphene film with an oxidized carbon-containing interfacial layer therebetween. In another embodiment, the PVD process can be used to form single or multiple monolayers of graphene.