Srinivasaraghavan, G.; Mukhopadhyay, A. A new necessary condition for the vertex visibility graphs of simple polygons. (English) Zbl 0812.05062 Discrete Comput. Geom. 12, No. 1, 65-82 (1994). For a simple polygon \(P\), let \(V\) be the set of vertices of \(P\) and \(E\) the set of pairs \((u,v)\) of vertices for which the segment \(\overline{uv}\) does not intersect the exterior of \(P\). The graph \(G= (V,E)\) is called the visibility graph of \(P\). Everett (Thesis 1989) conjectured that for a given graph \(G\) with a Hamiltonian cycle \(H\) to be the visibility graph of a polygon (and such that \(H\) corresponds to the boundary of \(P\)), the following condition is necessary: For every pair of vertices \((u,v)\) with \(\overline{uv}\not\in E\) there exists a blocking vertex \(w= B(u,v)\) in between, and such that \(B(u,v)= B(u',v')\) implies that \((u,v)\) and \((u',v')\) are not separable with respect to \(w\) on \(H\). The authors settle this conjecture in the affirmative by a sequence of lemmas. Reviewer: W.Weil (Karlsruhe) Cited in 4 Documents MSC: 05C99 Graph theory 52A30 Variants of convex sets (star-shaped, (\(m, n\))-convex, etc.) 52A10 Convex sets in \(2\) dimensions (including convex curves) 05C45 Eulerian and Hamiltonian graphs 52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) Keywords:simple polygon; visibility graph; Hamiltonian cycle PDFBibTeX XMLCite \textit{G. Srinivasaraghavan} and \textit{A. Mukhopadhyay}, Discrete Comput. Geom. 12, No. 1, 65--82 (1994; Zbl 0812.05062) Full Text: DOI EuDML References: [1] C. Coullard and A. Lubiw, Distance visibility graphs,Proceedings of the Seventh Annual ACM Symposium on Computational Geometry, 1991, pp. 289-296. · Zbl 0783.68091 [2] H. Everett, Recognizing Visibility Graphs, Ph.D. thesis, Department of Computer Science, University of Toronto, 1989. [3] S. K. Ghosh,On Recognizing and Characterizing Visibility Graphs of Simple Polygons, Lecture Notes in Computer Science, Vol. 318, Springer-Verlag, Berlin, 1988. · Zbl 1257.11035 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.