Crossing Numbers and Stress of Random Graphs

2018/08/22 by Chimani, Markus, Döring, Hanna, Reitzner, Matthias · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1808.07558

Abstract

Consider a random geometric graph over a random point process in ℝ^d. Two points are connected by an edge if and only if their distance is bounded by a prescribed distance parameter. We show that projecting the graph onto a two dimensional plane is expected to yield a constant-factor crossing number (and rectilinear crossing number) approximation. We also show that the crossing number is positively correlated to the stress of the graph's projection.

Cited by

• Using Reinforcement Learning to Optimize the Global and Local Crossing Number
• Existence of a plane without edge crossings in projections of the random geometric graph

Related

• Limit theorems for the number of crossings and stress in projections of the random geometric graph
• Existence of a plane without edge crossings in projections of the random geometric graph
• Crossings in Randomly Embedded Graphs
• The k-planar crossing number of random graphs and random regular graphs
• Plane and Planarity Thresholds for Random Geometric Graphs