- Visibility graph
A

**visibility graph**is a graph of intervisible locations. Each node or vertex in the graph represents a point location, and each edge represents avisible connection between them (that is, if two locations can see each other, an edge is drawn between them).Special classes are visibility graphs for points in the plane, in particular, within a

polygon . The polygon may or may not have "holes" (obstructions within the plan). A major open problem in this area is to characterize the visibility graphs of polygons.In addition to theoretical problems, visibility graphs also have practical uses, for example, to calculate the placement of radio antennas, or as a tool used within

architecture andurban planning throughvisibility graph analysis . Visibility graphs are also used in mobile robotics as a (generally offline)motion planning tool when the geometry of the environment is known, althoughrobot s have been designed that collectisovist information as they explore the environment usingultrasound sensor s, which can then be turned into a visibility graph of recognisable known locations.**ee also***

Art gallery problem **References*** cite book|author=O'Rourke, J.

authorlink = Joseph O'Rourke (professor)

year=1987|title=Art Gallery Theorems and Algorithms|publisher=Oxford University Press|id=ISBN 0-19-503965-3

* Chapter 15: Visibility Graphs: pp.307–317.**External links****oftware*** [

*http://www.VisiLibity.org VisiLibity: A free open source C++ library of floating-point visibility algorithms and supporting data types. This software can be used for calculating visibility graphs of polygonal environments with polygonal holes. A Matlab interface is also included.*]

*Wikimedia Foundation.
2010.*