That is, if the line segment connecting two locations does not pass through any obstacle, an edge is drawn between them in the graph.
[2] Lozano-Pérez & Wesley (1979) attribute the visibility graph method for Euclidean shortest paths to research in 1969 by Nils Nilsson on motion planning for Shakey the robot, and also cite a 1973 description of this method by Russian mathematicians M. B. Ignat'yev, F. M. Kulakov, and A. M. Pokrovskiy.
The visibility graph of a set of locations that lie in a line can be interpreted as a graph-theoretical representation of a time series.
Certain forms of the art gallery problem may be interpreted as finding a dominating set in a visibility graph.
The visibility graph approach to the Euclidean shortest path problem may be sped up by forming a graph from the bitangents instead of using all visibility edges, since a Euclidean shortest path may only enter or leave the boundary of an obstacle along a bitangent.