Geometric graphs with no two parallel edges |
| |
Authors: | Rom Pinchasi |
| |
Institution: | (1) Israel Institute of Technology Technion, Technion City, Haifa, 32000, Israel |
| |
Abstract: | 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. |
| |
Keywords: | 05C10 |
本文献已被 SpringerLink 等数据库收录! |
|