The Size of the Largest Components in Random Planar Maps
Zhicheng Gao, Nicholas Wormald · SIAM Journal on Discrete Mathematics · 1999
Bender, Richmond, and Wormald showed that in almost all planar 3-connected triangulations (or dually, 3-connected cubic maps) with n edges, the largest 4-connected triangulation (or dually, the largest cyclically 4-edge-connected cubic component) has about n/2 edges [ Random Structures Algorithms, 7 (1995), pp. 273--285]. In this paper, we derive some general results about the size of the largest component and apply them to a variety of types of planar maps.