Vertex-edge pseudo-visibility graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Vertex-edge pseudo-visibility graphs: characterization and recognition

Full text

Pdf (1.23 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the thirteenth annual symposium on Computational geometry table of contents

Nice, France

Pages: 119 - 128

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Joseph O'Rourke
Ileana Streinu	Department of Computer Science, Smith College, Northampton, MA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 25, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/262839.262915 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AK95	James Abello , Krishna Kumar, Visibility Graphs and Oriented Matroids, Proceedings of the DIMACS International Workshop on Graph Drawing, p.147-158, October 10-12, 1994
	BLW+93	A. BjSrner, M. Las Vergnas, N. White, B. Sturmfe Is, and G. Ziegler. Oriented Matroids. Cambridge University Press, Cambridge, 1993.
	Eve90	H. Everett, Visibility graph recognition, University of Toronto, Toronto, Ont., Canada, 1990
	Gho88	Subir Kumar Ghosh, On recognizing and characterizing visibility graphs of simple polygons, No. 318 on SWAT 88: 1st Scandinavian workshop on algorithm theory, p.96-104, January 1988, Halmstad, Sweden
	Gho97	S.K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons. Discrete Comput. Geom., 17(2):143- 162, 1997. Revision of {Gho88}.
	GP84	J.E. Goodman and R. Pollack. Semispaces of configurations, cell complexes of arrangements. J. Combin. Theory Set. A, 37:257-293, 1984.
	Knu92	D.E. Knuth. Axioms and Hulls, volume 606 of Lecture Notes in Computer Science. Springer-Verlag, Heidelberg, Germany, 1992.
	Mnë91	N.E. Mn#v. The universality theorem on the oriented matroid stratification of the space of real matrices, in J. E. Goodman, R. Pollack, and W. Steiger, editors, Discrete and Computational Geometry: Papers from the DIMACS Special Year, volume 6 of DIMA CS Series in Discrete Mathematics and Theoretical Computer Science, pages 237-243. AMS/ACM, 1991.
	O'R93	Joseph O'Rourke, Computational geometry column 18, ACM SIGACT News, v.24 n.1, p.20-25, Winter 1993 [doi>10.1145/152992.152994]
	OS96	J. O'Rourke and I. Streinu. Pseudovisibility graphs in pseudo-polygons: Part I. Technical Report 041, Dept. Comput. Sci., Smith College, Northampton, MA, January 1996. Revised Apr. 1996.
	OS97	Joseph O'Rourke , Ileana Streinu, The vertex-edge visibility graph of a polygon, Computational Geometry: Theory and Applications, v.10 n.2, p.105-120, May 1, 1998 [doi>10.1016/S0925-7721(97)00011-4]
	Sho91	P.W. Shor. Stretchability of pseudolines is NP-hard. In P. Gritzmann and B. Sturmfeis, editors, Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, volume 4 of DIMA CS Series in Discrete Mathematics and Theoretical Computer Science, pages 531-554. AMS Press, 1991.
	Str96a	Ileana Streinu, Clusters of stars, Proceedings of the thirteenth annual symposium on Computational geometry, p.439-441, June 04-06, 1997, Nice, France [doi>10.1145/262839.263074]
	Str96b	I. Streinu. Non-stretchable pseudovisibility graphs. Technical Report, Dept. Comput. Sei., Smith College, Northampton, MA, 1996.

CITED BY 7

	Pierre Angelier , Michel Pocchiola, A sum of squares theorem for visibility, Proceedings of the seventeenth annual symposium on Computational geometry, p.302-311, June 2001, Medford, Massachusetts, United States
	Ruth Haas , David Orden , Günter Rote , Francisco Santos , Brigitte Servatius , Hermann Servatius , Diane Souvaine , Ileana Streinu , Walter Whiteley, Planar minimally rigid graphs and pseudo-triangulations, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Ileana Streinu, Stretchability of star-like pseudo-visibility graphs, Proceedings of the fifteenth annual symposium on Computational geometry, p.274-280, June 13-16, 1999, Miami Beach, Florida, United States
	Ileana Streinu, Clusters of stars, Proceedings of the thirteenth annual symposium on Computational geometry, p.439-441, June 04-06, 1997, Nice, France
	Ruth Haas , David Orden , Günter Rote , Francisco Santos , Brigitte Servatius , Herman Servatius , Diane Souvaine , Ileana Streinu , Walter Whiteley, Planar minimally rigid graphs and pseudo-triangulations, Computational Geometry: Theory and Applications, v.31 n.1-2, p.31-61, May 2005
	Ileana Streinu, Non-stretchable pseudo-visibility graphs, Computational Geometry: Theory and Applications, v.31 n.3, p.195-206, June 2005
	Joseph S. B. Mitchell , Joseph O'Rourke, Computational geometry, ACM SIGACT News, v.32 n.3, p.63-72, 09/01/2001