A tight lower bound on the size of visibility graphs

H. Edelsbrunner, X. Shen, Information Processing Letters 26 (1987) 61–64.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Abstract
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
Volume
26
Issue
2
Page
61 - 64
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, 26(2), 61–64. 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 26, no. 2 (1987): 61–64. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar