Crossing Numbers and Stress of Random Graphs

Abstract

Consider a random geometric graph over a random point process in ${\mathbb{R}}^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.

Extended Version (compared to conference version @ GD)