New lower bounds for the number of ( k)-edges and the rectilinear crossing number of K_n
Given a set of \(n\) points \(S\) in general position in the plane, a \(j\)-edge (\(0\leq j\leq \lfloor (n-2)/2\rfloor\)) is a segment spanned by two points of \(S\) such that there are exactly \(j\) points in one of the open halfplanes defined by the line of the segment. A \((\leq k)\)-edge is a \(j\)-edge for some \(j=0,1,\dots,k\). The paper shows that for \(0\leq k\leq \lfloor (n-2)/2\rfloor\), the number of \((\leq k)\)-edges is at least \(3{k+2\choose 2} +\sum_{j=\lfloor n/3\rfloor}^k (3j-n+3)\), which improves the previous best lower bound of J. Balogh and G. Salazar, when \(\lfloor n/3 \rfloor \leq k \leq 0.4864n\). As consequence, an improved lower bound is obtained for the rectilinear lower bound of complete graphs, i.e. the minimum number of convex quadrilaterals determined by \(n\) points in the plane in general position. The new lower bound for the rectilinear crossing number of complete graphs is \(0.379688{n\choose 4} +O(n^3)\), the old lower bound was \(0.37533{n\choose 4} +O(n^3)\), while the best upper bound is \(0.380559{n\choose 4} +O(n^3)\). Particular new values of rectilinear crossing numbers have also been determined. The rectilinear crossing number of \(K_{19}\) is 1318 and of \(K_{21}\) is 2055.
- New results on lower bounds for the number of \((\leq k)\)-facets
- An improvement of the lower bound on the maximum number of halving lines in planar sets with 32 points
- On weighted sums of numbers of convex polygons in point sets
- \(k\)-sets and rectilinear crossings in complete uniform hypergraphs
- Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
- Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\)
- \(k\)-sets, convex quadrilaterals, and the rectilinear crossing number of \(K_{n}\)
- A lower bound for the rectilinear crossing number
- New results on lower bounds for the number of (⩽ k)-facets
- The maximum number of halving lines and the rectilinear crossing number of for
- On Center Regions and Balls Containing Many Points
- scientific article; zbMATH DE number 5555978 (Why is no real title available?)
- On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
- scientific article; zbMATH DE number 2079388 (Why is no real title available?)
- Bishellable drawings of K_n
- scientific article; zbMATH DE number 2145237 (Why is no real title available?)
- Extending drawings of complete graphs into arrangements of pseudocircles
- Turán's brick factory problem: the status of the conjectures of Zarankiewicz and Hill
- Graph Drawing
- Maximum rectilinear crossing number of uniform hypergraphs
- The 3-symmetric pseudolinear crossing number of \(K_{36}\)
- There is a unique crossing-minimal rectilinear drawing of \(K_{18}\)
- On polynomials associated to Voronoi diagrams of point sets and crossing numbers
- Levels in arrangements: linear relations, the g-matrix, and applications to crossing numbers
- Plane Hamiltonian cycles in convex drawings
- An extended lower bound on the number of( k)-edges to generalized configurations of points and the pseudolinear crossing number of K_n
- 3-symmetric and 3-decomposable geometric drawings of \(K_n\)
This page was built for publication: New lower bounds for the number of \((\leq k)\)-edges and the rectilinear crossing number of \(K_{n}\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2385147)
