An Improvement of the Lower Bound on the Minimum Number of ≤k-Edges
Open Access
- 3 March 2021
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 9 (5) , 525
Abstract
In this paper, we improve the lower bound on the minimum number of -edges in sets of n points in general position in the plane when k is close to . As a consequence, we improve the current best lower bound of the rectilinear crossing number of the complete graph for some values of n.
Keywords
This publication has 10 references indexed in Scilit:
- Thirty Essays on Geometric Graph Theory2013
- On ≤k-Edges, Crossings, and Halving Lines of Geometric Drawings of K nDiscrete & Computational Geometry, 2012
- New Lower Bounds for the Number of (≤ k)-Edges and the Rectilinear Crossing Number of KnDiscrete & Computational Geometry, 2007
- Improving the Crossing Lemma by Finding More Crossings in Sparse GraphsDiscrete & Computational Geometry, 2006
- A Lower Bound for the Rectilinear Crossing NumberGraphs and Combinatorics, 2005
- Convex quadrilaterals and 𝑘-sets2004
- Improved Bounds for Planar k -Sets and Related ProblemsDiscrete & Computational Geometry, 1998
- The number of small semispaces of a finite set of points in the planeJournal of Combinatorial Theory, Series A, 1986
- Crossing Number ProblemsThe American Mathematical Monthly, 1973
- Latest results on crossing numbers1971