We describe new phenomena of structural reorganization of carbon adsorbates as revealed by in situ atomic-resolution transmission electron microscopy (TEM) performed on specimens at extreme temperatures. In our investigations, a graphene sheet serves as both a quasi-transparent substrate for TEM and as an in situ heater. The melting of gold nanoislands deposited on the substrate surface is used to evaluate the local temperature profile. At annealing temperatures around 1000 K, we observe the transformation of physisorbed hydrocarbon adsorbates into amorphous carbon monolayers and the initiation of crystallization. At temperatures exceeding 2000 K the transformation terminates in the formation of a completely polycrystalline graphene state. The resulting layers are bounded by free edges primarily in the armchair configuration.