Multi-layer graphene flakes with superior properties can be produced by chemical vapor deposition (CVD) on Ni substrates over large areas. We report a detailed investigation of lateral structures corresponding to correlated variations in Ni roughness and multilayer graphene thickness uniformity that may form under certain conditions over the wafer with large (mm to cm) feature size. Investigating these structures is important for understanding the interplay between carbon diffusion, segregation, metal grain formation and its role on graphene growth. In this study, we investigated such structures formed after CVD graphene growth on 200 nm Ni thin films on SiO2 (300 nm)/Si substrates by optical microscopy, atomic force microscopy, scanning electron microscopy and Raman microscopy. Our findings showed large-scale Voronoi-like structures featuring roughness variations in the Ni film correlated with the thickness distribution of the graphene multilayers. Ni recrystallization during the CVD process plays a pivotal role in forming these structures. Similar roughness-related structures do not form without a source of carbon (methane) present during the process, which shows that carbon diffusion/segregation and Ni recrystallization are mutually dependent.