A central approach to bound the number of crossings in a generalized configuration

A generalized configuration is a set of n points and ((n; 2)) pseudolines such that each pseudoline passes through exactly two points, two pseudolines intersect exactly once, and no three pseudolines are concurrent. Following the approach of allowable sequences we prove a recursive inequality for the number of (≤k)-sets for generalized configurations. As a consequence we improve the previously best known lower bound on the pseudolinear and rectilinear crossing numbers from 0.37968 ((n; 4)) %2b Θ (n3) to 0.379972 ((n; 4)) %2b Θ (n3). © 2008 Elsevier B.V. All rights reserved.

≤ k-sets; complete graphs; k-sets; pseudolinear crossing number; rectilinear crossing number

VIVO