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

2017/09/24 by Asplund, John, Do, Thao, Hamm, Arran +3
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1709.08136

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 Ω((n²p)²). 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 Ω((dn)²) for d > c₀ for some constant c₀=c₀(k).

Related

• A survey of graphs with known or bounded crossing numbers
• New Bounds on the Biplanar and k-Planar Crossing Numbers
• Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs
• On the k-planar local crossing number
• New Bounds on the Biplanar Crossing Number of Low-dimensional Hypercubes