Abstract
A new necessary condition conjectured by Everett [2], which is essentially a stronger version of a necessary condition by Ghosh [3], for a graph to be the vertex visibility graph of a simple polygon is established.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C. Coullard and A. Lubiw, Distance visibility graphs,Proceedings of the Seventh Annual ACM Symposium on Computational Geometry, 1991, pp. 289–296.
H. Everett, Recognizing Visibility Graphs, Ph.D. thesis, Department of Computer Science, University of Toronto, 1989.
S. K. Ghosh,On Recognizing and Characterizing Visibility Graphs of Simple Polygons, Lecture Notes in Computer Science, Vol. 318, Springer-Verlag, Berlin, 1988.
Author information
Authors and Affiliations
Additional information
This work was carried out while G. Srinivasaraghavan was at the Indian Institute of Technology, Kanpur, India.
Rights and permissions
About this article
Cite this article
Srinivasaraghavan, G., Mukhopadhyay, A. A new necessary condition for the vertex visibility graphs of simple polygons. Discrete Comput Geom 12, 65–82 (1994). https://doi.org/10.1007/BF02574366
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574366