Publication | Closed Access
Visibility graph recognition
51
Citations
0
References
1990
Year
Unknown Venue
EngineeringPlanar GraphComputational ComplexityGraph ProcessingImage AnalysisSimple PolygonData ScienceStructural Graph TheoryGraph DrawingDiscrete MathematicsComputational GeometryGeometric Graph TheoryMachine VisionTopological Graph TheoryComputer ScienceComputer VisionGraph TheoryVisibility Graph RecognitionVisibility GraphVisibility GraphsGraph Analysis
The visibility graph of a simple polygon is a graph whose vertices correspond to the vertices of the polygon and whose edges correspond to pairs of polygon vertices that can see each other. Little is known about the combinatorial structure of visibility graphs despite their importance in computational geometry. We consider the recognition problem: given a graph, determine whether it is the visibility graph of a simple polygon. We provide two negative results: we disprove Ghosh's conjecture that his set of necessary conditions for a graph to be the visibility graph of a simple polygon is sufficient and we show that there is no finite set of forbidden induced subgraphs which characterize these graphs. In terms of positive results, we show that the recognition problem is in PSPACE, we show that some restricted classes of polygons have visibility graphs which belong to well known classes of graphs and we provide a linear time algorithm for recognizing the visibility graphs of spiral polygons.