Note on geometric graphs (Q1971016): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Disjoint edges in geometric graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A decomposition theorem for partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3048864 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Ramsey-Type Result for Convex Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4339095 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some geometric applications of Dilworth's theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Geometric graphs with few disjoint edges / rank | |||
Normal rank |
Latest revision as of 14:50, 29 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Note on geometric graphs |
scientific article |
Statements
Note on geometric graphs (English)
0 references
11 December 2000
0 references
The vertices of a geometric graph are points in the plane in a general position and the edges are (possibly crossing) line segments connecting the vertices. The article addresses the problem of determining the smallest number \( e_k(n) \) such that any geometric graph with \( n \) vertices and \( m > e_k(n) \) edges contains \( k+1 \) pairwise disjoint edges. The best previously known upper bound \( e_k(n) \leq k^3(n+1) \), for all \( k \leq n/2 \), is due to \textit{G. Tóth} and \textit{P. Valtr} [Geometric graphs with few disjoint edges, Discrete Comput. Geom. 22, No. 4, 633-642 (1999; Zbl 0939.68097)]. In the article under review, the upper bound is improved to \( e_k(n) \leq 2^9k^2n \), for all \( k < n/2 \), and this upper bound is shown to be sharp apart from the value of the constant for all \( k \) in \( O(\sqrt{n}) \). The nice simple proof of the upper bound takes advantage of a clever organization of the edges of the geometric graphs with no more than \( k \) pairwise disjoint edges into a limited number of length-limited ``zig-zag'' paths.
0 references
geometric graphs
0 references
pairwise disjoint edges
0 references