Carbon nanostructures (CNS) such as carbon nano-fibers (CNFs), -tubes (CNTs), and graphene are of interest for a diverse set of applications. Currently, these CNS are synthesized primarily by chemical vapor deposition (CVD) techniques, using metal catalysts. However, after CNS synthesis, those metals are oftentimes detrimental to the intended application, and extra steps for their removal, if available, have to be taken. As an alternative to metallic catalysts, metal oxide catalysts are investigated in order to better understand metal-free CVD processes for CNS synthesis. This thesis furthers the mechanistic understanding of metal oxide mediated CNS growth, especially metal oxide nanoparticles (MONPs) for CNTs, thereby addressing yield and expanding the range of known catalysts and atmospheric CVD conditions for CNS growth. CNT and CNF growth from zirconia nanoparticles (NPs) are first studied, and a technique is developed to grow CNTs and CNFs from metal NP (MNP) and MONP catalysts under identical CVD conditions. The morphologies of the catalyst-CNT and -CNF interface for zirconia NPs are found to be different than for iron or chromium NPs via high resolution transmission electron microscopy (HRTEM) including elemental and phase analyses, and evidence of surface-bound base growth mechanisms are observed for the zirconia NPs. Titania NP growth conditions are investigated parametrically to achieve homogeneous and relatively (vs. zirconia) high growth yield, where clusters of CNTs and CNFs separated by only tens of nanometers are observed. Catalytic activity of titania NPs are estimated to be an order of magnitude lower than iron NPs, and a lift-off mechanism for titania NP catalysts is described, indicating that several layers of graphene will cause lift-off, consistent with HRTEM observations of 4-5 layer graphite within the CNFs. Potential catalytic CNS activity of chromia, vanadia, ceria, lithia and alumina NPs are explored, establishing for the first time CNT growth from chromia and vanadia precursor-derived NPs, although the phases of those NPs are not determined during growth. The insights acquired from MONP-mediated CNS growth are applied to demonstrate continuous, high-yield, few-layer graphene formation on titania nanowires.