Geometric Graphs with No Three Disjoint Edges |
| |
| Authors: | Jakub Cerny |
| |
| Affiliation: | (1) Department of Applied Mathematics and Institute for Theoretical Computer Science, Charles University, Malostranske nam. 25, 118 00 Praha 1, Czech Republic |
| |
| Abstract: | ![]()
A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position and edges are represented by straight line segments. We show that a geometric graph on n vertices with no three pairwise disjoint edges has at most 2.5n edges. This result is tight up to an additive constant. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
