Forcing disjoint segments in the plane (Q1916059)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Forcing disjoint segments in the plane |
scientific article; zbMATH DE number 895875
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Forcing disjoint segments in the plane |
scientific article; zbMATH DE number 895875 |
Statements
Forcing disjoint segments in the plane (English)
0 references
2 July 1996
0 references
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.
0 references
geometric graph
0 references
plane
0 references
pairwise disjoint edges
0 references