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 the normal view instead:

scientific article; zbMATH DE number 895875
Language Label Description Also known as
default for all languages
No label defined
    English
    Forcing disjoint segments in the plane
    scientific article; zbMATH DE number 895875

      Statements

      Forcing disjoint segments in the plane (English)
      0 references
      0 references
      0 references
      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

      Identifiers