| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4647904 | Discrete Mathematics | 2012 | 5 Pages |
Abstract
Let GG be a geometric graph on nn vertices in general position in the plane. Suppose that for every line ℓℓ in the plane the subgraph of GG induced by the set of vertices in one of the two half-planes bounded by ℓℓ has at most kk edges (k≥1k≥1 may be a function of nn). Then GG has at most O(nk) edges. This bound is best possible.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Eyal Ackerman, Rom Pinchasi,