We discuss the synthesis of carbon nanotubes (CNTs) and graphene by catalytic chemical vapour deposition (CCVD) and plasma-enhanced CVD (PECVD), summarising the state-of-the-art understanding of mechanisms controlling their growth rate, chiral angle, number of layers (walls), diameter, length and quality (defects), before presenting a new model for 2D nucleation of a graphene sheet from amorphous carbon on a nickel surface. Although many groups have modelled this process using a variety of techniques, we ask whether there are any complementary ideas emerging from the different proposed growth mechanisms, and whether different modelling techniques can give the same answers for a given mechanism. Subsequently, by comparing the results of tight-binding, semi-empirical molecular orbital theory and reactive bond order force field calculations, we demonstrate that graphene on crystalline Ni(111) is thermodynamically stable with respect to the corresponding amorphous metal and carbon structures. Finally, we show in principle how a complementary heterogeneous nucleation step may play a key role in the transformation from amorphous carbon to graphene on the metal surface. We conclude that achieving the conditions under which this complementary crystallisation process can occur may be a promising method to gain better control over the growth processes of both graphene from flat metal surfaces and CNTs from catalyst nanoparticles.