Crossing numbers of random graphs
Joel Spencer, Gézá Tóth · Random Structures and Algorithms · 2002
Abstract The crossing number of G is the minimum number of crossing points in any drawing of G. We consider the following two other parameters. The rectilinear crossing number is the minimum number of crossing points in any drawing of G, with straight line segments as edges. The pairwise crossing number of G is the minimum number of pairs of crossing edges over all drawings of G. We prove several results on the expected values of these parameters of a random graph. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 347–358, 2002