Longest and shortest cycles in random planar graphs

Abstract

Let $P(n,m)$ be a graph chosen uniformly at random from the class of all planar graphs on vertex set $\{1,\dots ,n\}$ with $m=m(n)$ edges. We study the cycle and block structure of $P(n,m)$ when $m\sim n/2$. More precisely, we determine the asymptotic order of the length of the longest and shortest cycle in $P(n,m)$ in the critical range when $m=n/2+o(n)$. In addition, we describe the block structure of $P(n,m)$ in the weakly supercritical regime when $n^{2/3}\ll m-n/2\ll n$.

References in corpus (1)

• Probability asymptotics: notes on notation

Cited by in corpus (2)

• Local limit of sparse random planar graphs
• Two point concentration of maximum degree in sparse random planar graphs