Understanding the spatial structuring of animal behaviors and how they link landscapes can be critical for conservation management. This emerging field has been greatly facilitated by technologically advanced acquisition and analysis of data on animal movements. The framework of graph theory, which directly quantifies network connectivity properties, provides a useful addition to this tool set. Using a novel application of graph theory, we investigate the structure and patterning of African elephant Loxodonta africana rest sites, a potentially critical feature structuring spatial properties of animal populations. Elephants in the study rested intermittently and for short durations (1–3 rests d–1, lasting 3–5 h total). They switched circadian rest patterns according to landscape attributes, resting more during the day and further from permanent water in areas with high human density outside protected areas. Within protected areas and during the dry season, elephants showed clustering and sequential use of rest nodes (repeated motifs). Repeated use of specific rest nodes (self-looping) was more frequent than expected if rest nodes were chosen at random, particularly when outside protected areas further from water, indicating the importance of preferred rest sites. Our results suggest that elephants adjust resting behavior when in human-dominated areas, using preferred resting sites presumably in locations that reduce the risk of interactions. This study demonstrates how graph theory may be used practically to gain novel insight into behaviours, such as resting, that are discrete in time and space. Furthermore, analysis of the spatial and network properties of rest sites, given an individual's susceptibility when engaged in rest behavior, allowed characterization of spatio-temporal risk perception, providing a powerful behavioral based means to quantify the landscape of fear.