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

Font Size:  Small  Medium  Large

The distribution of the number of small cuts in a random planar triangulation

Zhicheng Gao, Gilles Schaeffer

Abstract


We enumerate rooted 3-connected (2-connected) planar triangulations with respect to the vertices and 3-cuts (2-cuts). Consequently, we show that the distribution of the number of 3-cuts in a random rooted 3-connected planar triangulation with n+3 vertices is asymptotically normal with mean (10/27)n and variance (320/729)n, and the distribution of the number of 2-cuts in a random 2-connected planar triangulation with n+2 vertices is asymptotically normal with mean (8/27)n and variance (152/729)n. We also show that the distribution of the number of 3-connected components in a random 2-connected triangulation with n+2 vertices is asymptotically normal with mean n/3 and variance 8 / 27n.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional