Skip to Main content Skip to Navigation
Conference papers

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

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 $\frac{8}{ 27}n$ .
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185596
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:33:47 PM
Last modification on : Tuesday, December 29, 2020 - 7:04:02 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:47:15 AM

File

dmAM0119.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185596, version 1

Collections

Citation

Zhicheng Gao, Gilles Schaeffer. The distribution of the number of small cuts in a random planar triangulation. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.277-288. ⟨hal-01185596⟩

Share

Metrics

Record views

269

Files downloads

724