Random Triangulations of the Plane

L. Bruce Richmond, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

18 Citations (Scopus)


It is shown that random 2- and 3-connected triangulations (bicubic maps) with 2n faces (vertices) almost certainly contain cn, c>0, copies of any particular 2- or 3-connected triangulation (bicubic map), respectively. Almost all 2- and 3-connected triangulations, and bicubic maps, with m vertices have longest path length less than cm, for some c < 1. If Barnette's conjecture that every 3-connected bicubic map is hamiltonian is false then almost all 3-connected bicubic maps are counterexamples to it.

Original languageEnglish
Pages (from-to)61-71
Number of pages11
JournalEuropean Journal of Combinatorics
Issue number1
Publication statusPublished - 1988
Externally publishedYes

Cite this