A tight lower bound on the size of visibility graphs
Edelsbrunner H, Shen X. 1987. A tight lower bound on the size of visibility graphs. Information Processing Letters. 26(2), 61–64.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Shen, Xiaojun
;
Shen, XiaojunAbstract
The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. This article proves that 5n - 4 is a lower bound on the number of edges in the visibility graph of n nonintersecting line segments in the plane. This bound is tight.
Publishing Year
Date Published
1987-10-19
Journal Title
Information Processing Letters
Publisher
Elsevier
Acknowledgement
Research of this author ‘was supported by the Amoco Foundation for Facilitation of Development of Computer
Science under Grant No. l-6-44862.
Volume
26
Issue
2
Page
61 - 64
ISSN
eISSN
IST-REx-ID
Cite this
Edelsbrunner H, Shen X. A tight lower bound on the size of visibility graphs. Information Processing Letters. 1987;26(2):61-64. doi:10.1016/0020-0190(87)90038-X
Edelsbrunner, H., & Shen, X. (1987). A tight lower bound on the size of visibility graphs. Information Processing Letters. Elsevier. https://doi.org/10.1016/0020-0190(87)90038-X
Edelsbrunner, Herbert, and Xiaojun Shen. “A Tight Lower Bound on the Size of Visibility Graphs.” Information Processing Letters. Elsevier, 1987. https://doi.org/10.1016/0020-0190(87)90038-X.
H. Edelsbrunner and X. Shen, “A tight lower bound on the size of visibility graphs,” Information Processing Letters, vol. 26, no. 2. Elsevier, pp. 61–64, 1987.
Edelsbrunner H, Shen X. 1987. A tight lower bound on the size of visibility graphs. Information Processing Letters. 26(2), 61–64.
Edelsbrunner, Herbert, and Xiaojun Shen. “A Tight Lower Bound on the Size of Visibility Graphs.” Information Processing Letters, vol. 26, no. 2, Elsevier, 1987, pp. 61–64, doi:10.1016/0020-0190(87)90038-X.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar