Crossing numbers of random graphs

DOI10.1002/RSA.10053MaRDI QIDQ4798172zbMATH OpenOpenAlexFDO

Authors Géza Tóth, Joel 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)

Recommendations

• Crossing numbers and stress of random graphs
• Crossing numbers of graphs
• scientific article; zbMATH DE number 2145247
• Crossing numbers of Sierpiński‐like graphs
• The Crossing Number of Graphs: Theory and Computation
• \(k\)-planar crossing number of random graphs and random regular graphs
• Survey of the crossing number of graphs
• Publication:4729111
• On the crossing number of complete graphs

Cites work

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

Cited in

(15)

• Crossing numbers and stress of random graphs
• Smoothed Analysis on Connected Graphs
• On the decay of crossing numbers of sparse graphs
• Space crossing numbers
• Counting extensions revisited
• Reappraising the distribution of the number of edge crossings of graphs on a sphere
• Approximating the rectilinear crossing number
• Analogies between the crossing number and the tangle crossing number
• scientific article; zbMATH DE number 2145247 (Why is no real title available?)
• Edge crossings in random linear arrangements
• Approximating the rectilinear crossing number
• Crossing number, pair-crossing number, and expansion
• \(k\)-planar crossing number of random graphs and random regular graphs
• Space crossing numbers
• Expected crossing numbers

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4798172)