Premium
Crossing numbers of random graphs
Author(s) -
Spencer Joel,
Tóth Géza
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10053
Subject(s) - crossing number (knot theory) , combinatorics , pairwise comparison , mathematics , random graph , graph , discrete mathematics , statistics , intersection (aeronautics) , geography , cartography
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