Crossing numbers of random graphs

DOI10.1002/rsa.10053zbMath1018.05023OpenAlexW2078972733MaRDI QIDQ4798172

Géza Tóth, J. H. Spencer

Publication date: 19 March 2003

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10053

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (7)

Crossing number, pair-crossing number, and expansion ⋮ Analogies between the crossing number and the tangle crossing number ⋮ On the Decay of Crossing Numbers of Sparse Graphs ⋮ Smoothed Analysis on Connected Graphs ⋮ Counting extensions revisited ⋮ Approximating the Rectilinear Crossing Number ⋮ Approximating the rectilinear crossing number

Cites Work

• Unnamed Item
• Unnamed Item
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
• Nearly perfect matchings in regular simple hypergraphs
• Which crossing number is it anyway?
• Toward the rectilinear crossing number of \(K _{n}\): New drawings, upper bounds, and asymptotics
• Applications of the crossing number
• Weighted sums of certain dependent random variables
• Counting extensions
• The number of polytopes, configurations and real matroids
• A Separator Theorem for Planar Graphs
• New lower bound techniques for VLSI
• Bounds for rectilinear crossing numbers
• Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
• Bisecting sparse random graphs
• Concentration of multivariate polynomials and its applications

This page was built for publication: Crossing numbers of random graphs