Characterizing bar line-of-sight graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Characterizing bar line-of-sight graphs

Full text

Pdf (360 KB)

Source

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

Baltimore, Maryland, United States

Pages: 147 - 152

Year of Publication: 1985

ISBN:0-89791-163-6

Author

Stephen K. Wismath

University of Lethbridge, University of British Columbia

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

Additional Information:

abstract 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/323233.323253 What is a DOI?

ABSTRACT

Line-of-sight graphs were introduced by Garey, Johnson and So in connection with a circuit testing problem. A restricted version of the problem (using line segments and a single line-of-sight) is discussed and the associated graphs are characterized. Results for directed and weighted cases are also presented.

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.

	1	[A] Algorithmic Aspects of Combinatorics, Annals of Discrete Math. 2 (1978), North Holland Publishing Co., p. 243.
	2	[Even] Even, S., Tarjan, R.; Computing an s-t Numbering: Theoretical Comp. Sci. 2 (1976), pp. 339-344.
	3	[GJS] Garey, M., Johnson, D., So, H.; An Application of Graph Coloring to Printed Circuit Testing; IEEE Trans. on Circuits and Systems, Vol. CAS23, No. 10, Oct. 1976, pp. 591-598.

CITED BY 5

	Giuseppe Di Battista , Ashim Garg , Giuseppe Liotta, An experimental comparison of three graph drawing algorithms (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.306-315, June 05-07, 1995, Vancouver, British Columbia, Canada
	L. Jackson , S. K. Wismath, Orthogonal polygon reconstruction from stabbing information, Computational Geometry: Theory and Applications, v.23 n.1, p.69-83, July 2002
	Joan P. Hutchinson, A note on rectilinear and polar visibility graphs, Discrete Applied Mathematics, v.148 n.3, p.263-272, 15 June 2005
	Joseph O'Rourke, Computational geometry column 18, ACM SIGACT News, v.24 n.1, p.20-25, Winter 1993
	R. Tamassia , J. S. Vitter, Optimal parallel algorithms for transitive closure and point location in planar structures, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.399-408, June 18-21, 1989, Santa Fe, New Mexico, United States