Improved Bounds for the Number of (<=k)-Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of K_n

Balogh, József and Salazar, Gelasio (2004) Improved Bounds for the Number of (<=k)-Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of K_n. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 25-35(Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_4).

Full text not available from this repository.

Abstract

We use circular sequences to give an improved lower bound on the minimum number of (<=k)-sets in a set of points in general position. We then use this to show that if S is a set of n points in general position, then the number $\square(S)$ of convex quadrilaterals determined by the points in S is at least $0.37553\binom{n}{4} + O(n^3)$. This in turn implies that the rectilinear crossing number $\overline{\hbox{\rm cr}}(K_n)$ of the complete graph K_n is at least $0.37553\binom{n}{4} + O(n^3)$. These improved bounds refine results recently obtained by Ábrego and Fernández-Merchant, and by Lovász, Vesztergombi, Wagner and Welzl.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_4
Classifications: A General Literature > A.001 Introductory and Survey
URI: http://gdea.informatik.uni-koeln.de/id/eprint/564

Actions (login required)

View Item View Item