Our scanning tunneling microscopy and X-ray photoelectron spectroscopy experiments along with first-principles calculations uncover the rich phenomenology and enable a coherent understanding of carbon vapor interaction with graphene on Ir(111). At high temperatures, carbon vapor not only permeates to the metal surface but also densifies the graphene cover. Thereby, in addition to underlayer graphene growth, upon cool down also severe wrinkling of the densified graphene cover is observed. In contrast, at low temperatures the adsorbed carbon largely remains on top and self-organizes into a regular array of fullerene-like, thermally highly stable clusters that are covalently bonded to the underlying graphene sheet. Thus, a new type of predominantly sp2-hybridized nanostructured and ultrathin carbon material emerges, which may be useful to encage or stably bind metal in finely dispersed form.