Editing Visibility graph (section)

==Applications==
Visibility graphs may be used to find [[Euclidean shortest path]]s among a set of [[polygon]]al obstacles in the plane: the shortest path between two obstacles follows straight line segments except at the [[vertex (geometry)|vertices]] of the obstacles, where it may turn, so the Euclidean shortest path is the shortest path in a visibility graph that has as its nodes the start and destination points and the [[vertex (geometry)|vertices]] of the obstacles.<ref name="robot">{{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2000}}, sections 5.1 and 5.3; {{harvtxt|Lozano-Pérez|Wesley|1979}}.</ref> Therefore, the Euclidean shortest path problem may be decomposed into two simpler subproblems: constructing the visibility graph, and applying a shortest path algorithm such as [[Dijkstra's algorithm]] to the graph. For planning the motion of a robot that has non-negligible size compared to the obstacles, a similar approach may be used after expanding the obstacles to compensate for the size of the robot.<ref name="robot"/> {{harvtxt|Lozano-Pérez|Wesley|1979}} attribute the visibility graph method for Euclidean shortest paths to research in 1969 by [[Nils Nilsson (researcher)|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.

Visibility graphs may also be used to calculate the placement of [[Antenna (radio)|radio antennas]], or as a tool used within [[architecture]] and [[urban planning]] through [[visibility graph analysis]].

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.<ref>{{cite journal |last1=Lacasa |first1=Lucas |last2=Luque |first2=Bartolo |last3=Ballesteros |first3=Fernando |last4=Luque |first4=Jordi |last5=Nuño |first5=Juan Carlos |title=From time series to complex networks: The visibility graph |journal=Proceedings of the National Academy of Sciences |date=2008 |volume=105 |issue=13 |pages=4972–4975 |doi=10.1073/pnas.0709247105|pmid=18362361 |pmc=2278201 |arxiv=0810.0920 |doi-access=free |bibcode=2008PNAS..105.4972L }}</ref> This particular case builds a bridge between [[time series]], [[dynamical systems]] and [[graph theory]].