a simple polygon. However, an efficient algorithmic characterization of the visibility graphs of simple polygons remains unknown. These graphs do not fall into many known families of well-structured graphs: they might not be perfect graphs, circle graphs, or chordal graphs. An exception to this phenomenon is that the visibility graphs of simple polygons are cop-win graphs. Related problems The art gallery problem is the problem of finding a small set of points such that all other non-obstacle points are visible from this set. Certain forms of the art gallery problem may be interpreted as finding a dominating set in a visibility graph. The bitangents of a system of polygons or curves are lines that touch two of them without penetrating them at their points of contact. The bitangents of a set of polygons form a subset of the visibility graph that has the polygon's vertices as its nodes and the polygons themselves as the obstacles. 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. See also Visibility graph analysis Fuzzy architectural spatial analysis Space syntax Notes References . . External links 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. Robot control Geometric graphs Computational geometry