Pach, JanosRubin, NatanTardos, Gabor2020-04-222020-04-222020-04-222019-01-0110.1145/3313276.3316328https://infoscience.epfl.ch/handle/20.500.14299/168313WOS:000523199100105We show that any set of n points in general position in the plane determines n(1-o(1)) pairwise crossing segments. The best previously known lower bound, Omega(root n), was proved more than 25 years ago by Aronov, Erdos, Goddard, Kreitman, Krugerman, Pach, and Schulman. Our proof is fully constructive, and extends to dense geometric graphs.Computer Science, Theory & MethodsComputer Sciencecomputational geometrygeometric graphsintersection graphscrossing edgesavoiding edgespartial orderscomparability graphsextremal combinatoricsstring graphsnumberpatternsboundsedgestext::conference output::conference proceedings::conference paper