Forcing disjoint segments in the plane (Q1916059)

From MaRDI portal
Revision as of 00:30, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Forcing disjoint segments in the plane
scientific article

    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
    0 references
    geometric graph
    0 references
    plane
    0 references
    pairwise disjoint edges
    0 references