2021/11/09 by Nikita Chernega, Chernega, Nikita, Alexandr Polyanskii +3
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2111.05425
openalex publication_date 2021/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A geometric graph is a graph drawn in the plane so that its vertices and edges are represented by points in general position and straight line segments, respectively. A vertex of a geometric graph is called pointed if it lies outside of the convex hull of its neighbours. We show that for a geometric graph with n vertices and e edges there are at least (n)/(2)\binom2e/n3 pairs of disjoint edges provided that 2e≥ n and all the vertices of the graph are pointed. Besides, we prove that if any edge of a geometric graph with n vertices is disjoint from at most m edges, then the number of edges of this graph does not exceed n(√(1+8m)+3)/4 provided that n is sufficiently large. These two results are tight for an infinite family of graphs.