Largest 4‐connected components of 3‐connected planar triangulations

Edward A. Bender, L. Bruce Richmond, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)

Abstract

Let Tn be a 3‐connected n‐vertex planar triangulation chosen uniformly at random. Then the number of vertices in the largest 4‐connected component of Tn is asymptotic to n/2 with probability tending to 1 as n → ∞. It follows that almost all 3‐connected triangulations with n vertices have a cycle of length at least n/2 + o(n).

Original languageEnglish
Pages (from-to)273-285
Number of pages13
JournalRandom Structures & Algorithms
Volume7
Issue number4
DOIs
Publication statusPublished - 1995
Externally publishedYes

Cite this