On the Diameter of Random Planar Graphs

Source abstract

We show that the diameter diam( G n ) of a random labelled connected planar graph with n vertices is equal to n 1/4+o(1) , in probability. More precisely, there exists a constant c > 0 such that $$ P(\D(G_n)\in(n^{1/4-\e},n^{1/4+\e}))\geq 1-\exp(-n^{c\e}) $$ for ε small enough and n ≥ n 0 (ε) . We prove similar statements for 2-connected and 3-connected planar graphs and maps.