Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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 Connect in order to contact the contributor
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

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, ⟨10.46298/dmtcs.2797⟩. ⟨hal-01185596⟩

Share

Metrics

Record views

153

Files downloads

419