k-planar crossing number of random graphs and random regular graphs

DOI10.1016/J.DAM.2018.04.007MaRDI QIDQ1671373zbMATH OpenOpenAlexFDO

Authors John Asplund, Arran Hamm, László A. Székely, Libby Taylor, Zhiyu Wang, Thao Do

Publication date 6 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.08136

zbMATH Keywords

crossing numberrandom graphsrandom regular graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: We give an explicit extension of Spencer's result on the biplanar crossing number of the Erdos-Renyi random graph $G(n,p)$. In particular, we show that the k-planar crossing number of $G(n,p)$ is almost surely $Omega((n^{2}p{)}^2)$. Along the same lines, we prove that for any fixed $k$, the $k$-planar crossing number of various models of random $d$-regular graphs is $Omega((dn{)}^2)$ for $d>c_0$ for some constant $c_0=c_0(k)$.

Recommendations

• Random planar graphs and the number of planar graphs
• scientific article; zbMATH DE number 2145247
• The number of planar graphs and properties of random planar graphs
• Crossing numbers of random graphs
• On random planar graphs, the number of planar graphs and their triangulations
• On the Number of Edges in Random Planar Graphs
• On \(k\)-planar crossing numbers
• On the crossing number of almost planar graphs
• On the Crossing Number of Almost Planar Graphs

Cites work

• A proof of Alon’s second eigenvalue conjecture and related problems
• Applications of the crossing number
• Explicit construction of linear sized tolerant networks
• scientific article; zbMATH DE number 2145247 (Why is no real title available?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(5)

• Crossing numbers and stress of random graphs
• Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method
• scientific article; zbMATH DE number 2145247 (Why is no real title available?)
• Crossing numbers of random graphs
• Limit theorems for the number of crossings and stress in projections of a random geometric graph

This page was built for publication: \(k\)-planar crossing number of random graphs and random regular graphs

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