We give a simple proof for a theorem of Katchalski, Last, and Valtr, asserting that the maximum number of edges in a geometric graph G on n vertices with no pair of parallel edges is at most 2n - 2. We also give a strengthening of this result in the case where G does not contain a cycle of length 4. In the latter case we show that G has at most 3/2(n - 1) edges.
展开▼
