Visibility analysis based on viewsheds is one of the most frequently used GIS analysis tools. In this paper we present an approach to visibility analysis based on the visibility graph. A visibility graph records the pattern of mutual visibility relations in a landscape, and provides a convenient way of storing and further analysing the results of multiple viewshed analyses for a particular landscape region. We describe how a visibility graph may be calculated for a landscape. We then give examples, which include the interactive exploration of a landscape, and the calculation of new measures of a landscape's visual properties based on graph metrics-in particular, neighbourhood clustering coefficient and path length analysis. These analyses suggest that measures derived from the visibility graph may be of particular relevance to the growing interest in quantifying the perceptual characteristics of landscapes.