科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let G be a geometric graph on n vertices in general position in the plane. We say that G is k-light if no edge e of G has the property that each of the two open half-planes bounded by the line through e contains more than k edges of G. We extend the previous result in Ackerman and Pinchasi (2012)[1] and with a shorter argument show that every k-light geometric graph on n vertices has at most O(n root k) edges. This bound is best possible.
- 出版日期2013-6-28
