Current approaches that compare spatial genetic structure of a given species and the dispersal of its mobile phase can detect a mismatch between both patterns mainly due to processes acting at different temporal scales. Genetic structure result from gene flow and other evolutionary and demographic processes over many generations, while dispersal predicted from the mobile phase often represents solely one generation on a single time-step. In this study, we present a spatial graph approach to landscape genetics that extends connectivity networks with a stepping-stone model to represent dispersal between suitable habitat patches over multiple generations. We illustrate the approach with the case of the striped red mullet Mullus surmuletus in the Mediterranean Sea. The genetic connectivity of M. surmuletus was not correlate with the estimated dispersal probability over one generation, but with the stepping-stone estimate of larval dispersal, revealing the temporal scale of connectivity across the Mediterranean Sea. Our results highlight the importance of considering multiple generations and different time scales when relating demographic and genetic connectivity. The spatial graph of genetic distances further untangles intra-population genetic structure revealing the Siculo-Tunisian Strait as an important corridor rather than a barrier for gene flow between the Western- and Eastern Mediterranean basins, and identifying Mediterranean islands as important stepping-stones for gene flow between continental populations. Our approach can be easily extended to other systems and environments.