Large-scale water scarcity indicators have been widely used to map and inform decision makers and the public about the use of river flows, a vital and limited renewable resource. However, spatiotemporal interrelations among users and administrative entities are still lacking in most large-scale studies. Water scarcity and interrelations are at the core of the water-ecosystem-energy-food nexus. In this paper, we balance water availability in the Black Sea catchment with requirements and consumptive use of key water users, i.e., municipalities, power plants, manufacturing, irrigation and livestock breeding, accounting for evaporation from major reservoirs as well as environmental flow requirements. We use graph theory to highlight interrelations between users and countries along the hydrological network. The results show that water scarcity occurs mainly in the summer due to higher demand for irrigation and reservoir evaporation in conjunction with relatively lower water resources, and in the fall-winter period due to lower water resources and the relatively high demand for preserving ecosystems and from sectors other than irrigation. Cooling power plants and the demands of urban areas cause scarcity in many isolated locations in the winter and, to a far greater spatial extent, in the summer with the demands for irrigation. Interrelations in water scarcity-prone areas are mainly between relatively small, intra-national rivers, for which the underlying national and regional governments act as key players in mitigating water scarcity within the catchment. However, many interrelations exist for larger rivers, highlighting the need for international cooperation that could be achieved through a water-ecosystem-energy-food nexus.