DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Font Size:  Small  Medium  Large

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

Valid XHTML 1.0 Transitional