Crossing Numbers of Random Graphs

Joel Spencer; Géza Tóth

doi:10.1002/rsa.10053

Crossing Numbers of Random Graphs

Joel Spencer, Géza Tóth

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	347-358
Number of pages	12
Journal	Random Structures and Algorithms
Volume	21
Issue number	3-4
DOIs	https://doi.org/10.1002/rsa.10053
State	Published - 2002

ASJC Scopus subject areas

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1002/rsa.10053

Cite this

@article{b5847f932fd04c7cb344400f0d2b6615,

title = "Crossing Numbers of Random Graphs",

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.",

author = "Joel Spencer and G{\'e}za T{\'o}th",

year = "2002",

doi = "10.1002/rsa.10053",

language = "English (US)",

volume = "21",

pages = "347--358",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "3-4",

}

TY - JOUR

T1 - Crossing Numbers of Random Graphs

AU - Spencer, Joel

AU - Tóth, Géza

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0242330697&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0242330697&partnerID=8YFLogxK

U2 - 10.1002/rsa.10053

DO - 10.1002/rsa.10053

M3 - Article

AN - SCOPUS:0242330697

SN - 1042-9832

VL - 21

SP - 347

EP - 358

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 3-4

ER -

Crossing Numbers of Random Graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this