Editing Visibility graph (section)

==Characterization==
The visibility graph of a [[simple polygon]] has the polygon's vertices as its point locations, and the exterior of the polygon as the only obstacle. Visibility graphs of simple polygons must be [[Hamiltonian graph]]s: the boundary of the polygon forms a Hamiltonian cycle in the visibility graph. It is known that not all visibility graphs induce 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 graph]]s, [[circle graph]]s, or [[chordal graph]]s.<ref>{{Cite journal|title = On recognizing and characterizing visibility graphs of simple polygons|journal = Discrete & Computational Geometry|date = 1997-03-01|issn = 0179-5376|pages = 143–162|volume = 17|issue = 2|doi = 10.1007/BF02770871|first = S. K.|last = Ghosh|doi-access = free}}</ref> An exception to this phenomenon is that the visibility graphs of simple polygons are [[cop-win graph]]s.<ref>{{cite journal
 | last1 = Lubiw | first1 = Anna | author1-link = Anna Lubiw
 | last2 = Snoeyink | first2 = Jack
 | last3 = Vosoughpour | first3 = Hamideh
 | arxiv = 1601.01298
 | doi = 10.1016/j.comgeo.2017.07.001
 | journal = [[Computational Geometry (journal)|Computational Geometry]]
 | mr = 3693353
 | pages = 14–27
 | title = Visibility graphs, dismantlability, and the cops and robbers game
 | volume = 66
 | year = 2017}}</ref>