Crossing Numbers of Random Graphs

Joel Spencer, Géza Tóth

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)347-358
Number of pages12
JournalRandom Structures and Algorithms
Volume21
Issue number3-4
DOIs
StatePublished - 2002

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Crossing Numbers of Random Graphs'. Together they form a unique fingerprint.

Cite this