A computational method has been developed for generating graphitic carbon structures on an arbitrary smooth surface and with a given number of carbon rings. Using both periodic and random surfaces for constraint, many extended graphitic carbon structures have been generated. The energy relative to graphite and the bulk clastic properties have been calculated. Like their periodic counterparts, the random structures are found to be exceptionally stable. Their radial distribution functions match closely those of films of amorphous carbon grown on NaCl substrates from sublimated graphite.