We study epitaxial graphene on the 6H-SiC(0001) surface under ambient conditions using frequency-modulation atomic force microscopy. We observe large terraces with a self-assembled stripe structure within a highly adsorbate covered surface on top of the graphene. To identify the origin of the structure, we compare the experimental data on graphene with calculations and experiments on graphite that predict the formation of a solid-gas monolayer in the solid-liquid interface of hydrophobic surfaces.