Vertex-edge pseudo-visibility graphs
Joseph O’Rourke, Ileana Streinu · 1997
We extend the notion of polygon visibility graphs to pseud~polygons defined on genemlized conjigumtions Of points.We consider both vertex-to-vertex, as well as vertex-to-edge visibility in pseudo-polygons.We study the characterization and recognition problems for vertex-edge pseudo-visibility graphs.Given a bipart.itegraph G satisfying three simple properties, which can all be checked in polynomial time, we show that we can define a generalized configuration of points and a pseudo-polygon on it, so that its vertexedge pseudo-visibility graph is G. This provides a full characterization of vertex-edge pseudo-visibility graphs and a polynomial-time algorithm for the decision problem. It also implies that the decision problem for vertex visibilitygraphs of pseud~polygons is in NP(as opposed to the same problem with straight-edge visibility, which is only known to be in PSPACE). 1 Introduction Characterizing visibility graphs has remained an elusive problem [0'R93].Ghosh [Gho88, Gho97] pro posed a set of necessary conditions as a starting point. Everett ~ve90] proved their insufficiency and proposed new conditions. She also placed the recognition problem in PSPACE by reducing it to the existential theory of the reals. Abello and Kumar [AK95]expanded the set of conditions and first related the problem with oriented matroid theory.Their conditions, plus realizability (stretchability) of a certain "