An Improvement of the Lower Bound on the Minimum Number of <=k-Edges

Abstract

En este artículo se mejora la cota inferior del mínimo número de <=k-edges para conjuntos de n punros del plano en posición general, cuando k está cerca de n/2. Como consecuencia, se mejora la actual mejor cota inferior del rectilinear crossing number para grafos completos de n vértices y algunos valores de n.

In this paper, we improve the lower bound on the minimum number of≤k-edges in sets of n points in general position in the plane when k is close to n/2. As a consequence, we improve the current best lower bound of the rectilinear crossing number of the complete graph Kn for some values of n.