On degrees in random triangulations of point sets

DOI10.1016/j.jcta.2011.04.002zbMath1232.05217OpenAlexW2025525764WikidataQ54308631 ScholiaQ54308631MaRDI QIDQ549246

Adam Sheffer, Micha Sharir, Ermo Welzl

Publication date: 7 July 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcta.2011.04.002

zbMATH Keywords

random graphstriangulationscombinatorial geometrycharging schemes

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial geometries and geometric closure systems (51D20)

Related Items (8)

A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set ⋮ An exact algorithm for the minimum dilation triangulation problem ⋮ The Mathematics of Ferran Hurtado: A Brief Survey ⋮ A QPTAS for the base of the number of crossing-free structures on a planar point set ⋮ On numbers of pseudo-triangulations ⋮ Counting Plane Graphs: Cross-Graph Charging Schemes ⋮ Counting triangulations and other crossing-free structures approximately ⋮ Counting triangulations and other crossing-free structures via onion layers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting triangulations of planar point sets
• Note on the number of triangulations of planar point sets
• A pattern of asymptotic vertex valency distributions in planar maps
• The four-colour theorem
• Random planar graphs
• A better upper bound on the number of triangulations of a planar point set
• A lower bound on the number of triangulations of planar point sets
• Crossing-Free Subgraphs
• Number of Crossing-Free Geometric Graphs vs. Triangulations

This page was built for publication: On degrees in random triangulations of point sets