Longest and shortest cycles in random planar graphs. Issue 3 (18th August 2021) - Kang, Mihyun; Missethan, Michael
Abstract: Let P ( n, m ) be a graph chosen uniformly at random from the class of all planar graphs on vertex set 1, …, n with m = m ( n ) edges. We study the cycle and block structure of P ( n, m ) when m ∼ 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 ≪ m − n / 2 ≪ n .