A better understanding of the interface configuration is likely to play an important role in the heteroepitaxial growth of nanostructure. Here, the structure and deposition characteristics of Zn atoms on fixed graphene, Si (001) and graphene/Si (001) substrates are investigated for the ZnO nanostructure growth through using Monte Carlo simulations. Highly ordered heteroepitaxial structures of Zn atoms are obtained on the different substrates. The pair distribution functions, density distributions perpendicular to the surface and the common neighbor analysis are used to characterize the thermal and structural evolutions of these Zn atoms. Features such as interlayer spacing and different substrates that influence the deposition process are studied qualitatively and quantitatively. Investigation shows that the lattice structures of substrates have a significant influence on the resultant heteroepitaxial structure in the overlayer material. These findings provide a sound physical insight for ZnO nanostructure growth on the different substrates. (C) 2011 Elsevier B.V. All rights reserved.