Forcing disjoint segments in the plane (Q1916059): Difference between revisions

A geometric graph is a graph drawn in the plane such that its edges are closed line segments and no three vertices are colinear. Denoting by \(n\) the number of vertices and by \(m\) the number of edges, the following hold: (i) if \(m\geq 3n+ 1\), then there exist three pairwise disjoint edges; (ii) if \(m\geq 10n+ 1\), then there exist four pairwise disjoint edges; (iii) if \(m\geq c_k n(\log n)^{k- 4}\), then there exist \(k\) pairwise disjoint edges. However, \textit{J. Pach} and \textit{J. Töröcsik} have shown in [Some geometric applications of Dilworth's theorem, Discrete Comput. Geom. 12, No. 1, 1-7 (1994; Zbl 0799.05018)], that if \(m\geq k^4n+ 1\), then there exist \(k+ 1\) pairwise disjoint edges.