Longest and shortest cycles in random planar graphs. Issue 3 (18th August 2021)

• Record Type: Journal Article
• Authors: Kang, Mihyun; Missethan, Michael
• Is Part Of: Random structures & algorithms. Volume 60:Issue 3(2022)
• Page Start: 462
• Page End: 505
• Publication Date: 2021-08-18
• Subjects: blocks -- cycles -- planar graphs -- Pólya urn -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21040
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .