We show that it is possible to prepare and identify ultra--thin sheets of graphene on crystalline substrates such as SrTiO$_3$, TiO$_2$, Al$_2$O$_3$ and CaF$_2$ by standard techniques (mechanical exfoliation, optical and atomic force microscopy). On the substrates under consideration we find a similar distribution of single, bi- and few layer graphene and graphite flakes as with conventional SiO$_2$ substrates. The optical contrast $C$ of a single graphene layer on any of those substrates is determined by calculating the optical properties of a two-dimensional metallic sheet on the surface of a dielectric, which yields values between $C=$ ~- 1.5% (G/TiO$_2$) and $C=$ ~- 8.8% (G/CaF$_2$). This contrast is in reasonable agreement with experimental data and is sufficient to make identification by an optical microscope possible. The graphene layers cover the crystalline substrate in a carpet-like mode and the height of single layer graphene on any of the crystalline substrates as determined by atomic force microscopy is $d_{SLG}=0.34$ nm and thus much smaller than on SiO$_2$.