Random triangulations of the plane

DOI10.1016/S0195-6698(88)80028-3MaRDI QIDQ1114717zbMATH OpenFDO

Authors L. Bruce Richmond, Nicholas Wormald

Publication date 1988

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0195-6698(88)80028-3

zbMATH Keywords

bicubic mapshamiltoniantriangulations

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph theory (05C99) Polytopes and polyhedra (52Bxx)

Review text

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.

Recommendations

• Random Triangles and Polygons in the Plane
• Random triangulations of planar points sets
• Random triangles in planar regions
• Random Triangles in n Dimensions
• scientific article; zbMATH DE number 3881565
• Generating triangulations at random
• RANDOM POLYGONS DETERMINED BY RANDOM LINES IN A PLANE
• Random triangles on flat tori
• Triangles in random cubic planar graphs
• Computing and Combinatorics

Cites work

• A Census of Planar Maps
• A Census of Planar Triangulations
• A Remark on Stirling's Formula
• A Theorem on Planar Graphs
• Asymptotic Methods in Enumeration
• Enumeration of cyclically 4-connected cubic graphs
• scientific article; zbMATH DE number 3908476 (Why is no real title available?)
• scientific article; zbMATH DE number 3494458 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• scientific article; zbMATH DE number 3412677 (Why is no real title available?)
• On Hamiltonian Circuits
• On the enumeration of convex polyhedra
• Simple paths on convex polyhedra

Cited in

(21)

• Graph structural properties of non-Yutsis graphs allowing fast recognition
• A survey of the asymptotic behaviour of maps
• Uniform infinite planar triangulations
• Asymptotic normality determined by high moments, and submap counts of random maps
• The asymptotic number of rooted maps on a surface. II: Enumeration by vertices and faces
• Random planar shapes and their statistical recognition
• Distributions of near-4-regular maps on the sphere and the projective plane
• Random triangles in planar regions
• Exponents for Hamiltonian paths on random bicubic maps and KPZ
• Random Triangles and Polygons in the Plane
• scientific article; zbMATH DE number 3908476 (Why is no real title available?)
• The Size of the Largest Components in Random Planar Maps
• Random triangles
• Largest 4‐connected components of 3‐connected planar triangulations
• Generating triangulations at random
• THE SIERPINSKI TRIANGLE PLANE
• On longest paths and diameter in random Apollonian networks
• RANDOM POLYGONS DETERMINED BY RANDOM LINES IN A PLANE
• Asymptotic normality of pattern occurrences in random maps
• Hamiltonian cycles in cubic 3-connected bipartite planar graphs
• The bivariate Ising polynomial of a graph

This page was built for publication: Random triangulations of the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114717)