Existence of a plane without edge crossings in projections of the random geometric graph

2025/07/14 by de Jonge, Lianne
#60D05 #60F05 #68R10 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2507.10389

Abstract

Consider a random geometric graph G on on a convex body W⊂ ℝ³ with a vertex set defined by a Poisson point process with intensity t>0. Then G can be drawn on a plane L by projecting all vertices onto L and connecting each pair of vertices by a line segment whenever there is exists and edge between them. Rotations of the plane L lead to different drawings. In this paper, we prove that the probability that there exists a plane such that there are no edge crossings in the projection tends to one if the connection radius is smaller than (c^* (log t)/(t⁴))^1/8 for some c^*>0.

Citations

• Limit theorems for the number of crossings and stress in projections of the random geometric graph
• Poisson approximation with applications to stochastic geometry
• Crossing Numbers and Stress of Random Graphs

Related

• Limit theorems for the number of crossings and stress in projections of the random geometric graph
• Crossing Numbers and Stress of Random Graphs
• Plane and Planarity Thresholds for Random Geometric Graphs
• On the One dimensional Poisson Random Geometric Graph
• Localization in random geometric graphs with too many edges