Stretchability of star-like pseudo-visibility graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Stretchability of star-like pseudo-visibility graphs

Full text

Pdf (798 KB)

Source

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

Miami Beach, Florida, United States

Pages: 274 - 280

Year of Publication: 1999

ISBN:1-58113-068-6

Author

Ileana Streinu

Dept. 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): 2, Downloads (12 Months): 12, Citation Count: 5

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/304893.304980 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
	BPR	Saugata Basu , Richard Pollack , Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM (JACM), v.43 n.6, p.1002-1045, Nov. 1996 [doi>10.1145/235809.235813]
	Bj93	A. BjSrner, M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler. Oriented Matroids, Cambridge University Press, 1993
	Bo93	J. Bokowski. Oriented Matroids, in P.M. Gruber and J.M. Wills (eds.), Handbook of Convex Geometry, North Holland, vol. A and B, pp.555-602, 1993.
	BS89a	J. Bokowski and B. Sturmfels, Computational Synthetic Geometry, Springer Verlag, LNM 1355, 1989.
	BS89b	J. Bokowski and B. Sturmfels, An Infinite Family of Minor-Minimal Nonrealizable 3- Chirotopes, Math.Zeitschrift 200, 583-589, 1989.
	BRS90	Jürgen Bokowski , Jürgen Richter , Bernd Sturmfels, Nonrealizability proofs in computational geometry, Discrete & Computational Geometry, v.5 n.4, p.333-350, Jul. 1990 [doi>10.1007/BF02187794]
	Ca88	John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
	Ca88	J. Canny. Improved algorithms }or sign determination and existential quantifier elimination, The Computer Journal, 36, 1993, pp. 409-418.
	Ev89	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:143-162, 1997.
	GP80	J.E. Goodman and R. Pollack. On the combinatorial classification of non-degenerate configurations in the plane. J. Combinat. Theory, ser. A 29 (1980), 220-235.
	GP84	J.E. Goodman and R. Pollack. Semispaces of configurations, cell complexes of arrangements, J. of Combinatorial Theory, Series A, 37:257-293, 1984.
	GP93	J.E. Goodman and R. Pollack. Allowable sequences and Order Types in Discrete and Computational Geometry, in New Trends in Discrete and Computational Geometry, J. Pach (ed.), Springer Verlag, 1993
	Go97	Jacob E. Goodman, Pseudoline arrangements, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	Gr72	B. Griinbaum. Arrangements and Spreads Regional Conf. Ser. Math., Amer. Math. Soc., number 10, Providence, RI, 1972.
	Lo	L. Lovasz. Problems o} Combinatorics, Academic Press, 1975.
	Mn91	N. Mn#v. The Universality Theorem on the Oriented Matroid Stratification of the Space of Real Matrices, in Discrete and Computational geometry, DIMACS Special Year (eds. J. Goodman, R. Pollack and W. Steiger), AMS/ACM DIMACS Series in Discrete Math. and Theoretical Computer Science, vol. 6, 1991.
	Ri89	J. Richter. Kombinatorische Realisierbarkeitskriterien fiir orientierte Matroide, Diplomarbeit, TH Darmstadt, 1989
	Ri91	J. Richter-Gebert. On the realisability problem for combinatorial geometries- decision methods, dissertation, TH Darmstadt, 1991.
	OS98	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]
	ORS96	Joseph O'Rourke , Ileana Streinu, Vertex-edge pseudo-visibility graphs: characterization and recognition, Proceedings of the thirteenth annual symposium on Computational geometry, p.119-128, June 04-06, 1997, Nice, France [doi>10.1145/262839.262915]
	Sh91	P. Shor. Stretchability of Pseudolines is NP- Hard, in Applied Geometry and Discrete Mathematics, the Victor Klee Festscrift, P. Gritzmann, B. Sturmfels (eds.), DIMACS Series in Discrete Math. and Theoretical Computer Science, vol. 4, 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 Pseudo-Visibility Graphs Smith College Computer Science Department Tech Report, 1996.

CITED BY 5

	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
	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
	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