Uniform Geodesic Drawings of Graphs

Abstract

We study crossing numbers of dense graph drawings whose vertices are uniformly distributed either on the unit sphere or in a compact convex planar domain. We prove a sharp inequality for weighted geodesic drawings on ${\mathbb{S}}^2$ in a continuous setting: among all measurable edge arrangements of a fixed density, the amount of crossings is minimized by connecting pairs of points within a fixed distance threshold. We also prove a planar analogue for straight-line drawings in convex planar domains. We transfer these continuous results to finite graphs using a smoothing argument. In the small density limit, we recover the conjectured midrange crossing constant lower bound of $8/(9\ddot{I}{€}^2)$ for this restricted model.

16 pages, 2 figures