2017/04/10 by Siddharth Prasad, Prasad, Siddharth
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1704.03066
openalex publication_date 2017/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We explore various techniques for counting the number of straight-edge crossing-free graphs that can be embedded on a planar point set. In particular, we derive a lower bound on the ratio of the number of such graphs with m+1 edges to the number of graphs with m edges. We show how a relatively small improvement of this bound would improve existing bounds concerning numbers of plane graphs with a prescribed number of edges. Furthermore, we use a cross-graph charging scheme to derive lower bounds for the number of such graphs when the point set has few extreme points.