×

A new necessary condition for the vertex visibility graphs of simple polygons. (English) Zbl 0812.05062

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)

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.)
PDFBibTeX XMLCite
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.