On the diameter of random planar graphs
Guillaume Chapuy, Éric Fusy, Omer Giménez, Marc Noy
Abstract
We show that the diameter D(Gn) of a random (unembedded) labelled connected planar graph with n vertices is asymptotically almost surely of order n1/4, in the sense that there exists a constant c>0 such that P(D(Gn)∈(n1/4-ε,n1/4+ε))≥1-&exp;(-ncε) for ε small enough and n large enough (n≥n0(ε)). We prove similar statements for rooted 2-connected and 3-connected embedded (maps) and unembedded planar graphs.
Full Text: PostScript PDF