Abstract: Graphene-supported platinum (Pt) and palladium (Pd) nanoclusters have attracted attention as electrocatalysts for proton exchange membrane fuel cell (PEMFC) because of their high activity and resistance to CO poisoning. However, metal nanoparticles are weakly adsorbed to the graphene and easily migrate on the surface, causing sintering and loss of chemical activity. A thorough understanding of structure-adsorption relationship is important to design robust catalysts with high adsorption ability to stabilize metal nanoparticles, but this relationship is still not well understood, particularly in large scale systems (2–5 nm). Therefore, to investigate the structural evolution at atomic scale with atomistic simulations, we have developed interatomic potentials for the Pt-C and Pd-C binary systems, based on the second nearest-neighbor modified embedded-atom method (2NN MEAM) formalism. These potentials reproduce various fundamental properties of the alloy systems in reasonable agreement with the experimental data and first-principles calculations. Molecular dynamics simulations employing the 2NN MEAM potential were carried out to analyse structural factors that have decisive effect on the adsorption energy, by changing the symmetry of the nanoparticles and the configuration of the nanoparticles adsorbed to graphene. These factors were characterized via coordination numbers, number of Pt atoms in contact with the graphene and adsorption site. The results of our study suggest avenues for stabilizing and immobilizing metal clusters on graphene in large systems.