Spatial orientation and spatial navigation are important abilities. However, large individual differences are common in these spatial abilities, yet satisfying explanations about the origin of such differences are lacking. In this work, we measured the eye-tracking data of 26 participants who freely explored a large city (244 buildings) in an immersive virtual reality for 150 min. After the exploration, participants performed a pointing-to-building task in the same city. For the analysis, we transform the eye-tracking data into gaze-graphs and calculate graph-theoretical measures. We then model participants' mean task performance with a linear model using global gaze-graph measures (R²=0.41). Moreover, a linear model with graph diameter only results in an R² of 0.4; thus, graph diameter can explain 40% of the variance in the mean task performance of participants. Overall, our results show visual behavior, specifically gaze-graph diameter, to be a strong predictor of individual differences in spatial navigation performance.