We examine the robustness of centralized, landbound relief operations’ capability to promptly reach areas affected by a disaster event from a network perspective. We initially look at two idealized road networks: a two-dimensional grid and a scale-free network, and compare them to an actual road network obtained from OpenStreetMap. We show that, from a node designated as the center for relief operations (a ‘relief center’), damage to a road network causes a substantial fraction of the other nodes (about 20% in the three networks we examined) to become initially inaccessible from any relief effort, although the remaining majority can still be reached readily. Furthermore, we show the presence of a threshold in the two idealized road networks but not in the real one. Below this threshold, all nodes can robustly be reached in a short span of time, and above it, not only the partitioning mentioned above sets in, but also the time needed to reach the nodes becomes susceptible to the amount of damage sustained by the road network. Under damage sustained by random segments of the network, this threshold is higher in the scale-free network compared to the grid, due to the robustness of the former against random attacks. Our results may be of importance in formulating contingency plans for the logistics of disaster relief operations.