On the geodesic midrange crossing constant

Abstract

We introduce an analytic framework for studying the number of crossings in planar straight-line and spherical geodesic drawings; we begin by analyzing drawings in a continuous setting and then pass to finite graphs. We use this approach to derive multiple results. First, we show that the midrange crossing constant is strictly smaller than $8/(9{\pi }^2)$, improving the best known upper bound of Pach and Tóth from nearly thirty years ago. Second, we prove sharp lower bounds for some restricted drawing classes. For spherical geodesic drawings with uniformly distributed vertices, we determine the minimum number of crossings at every edge density. We also prove lower bounds for planar straight line drawings in compact convex domains with uniform vertex sets. Consequently, we determine the restricted midrange crossing constant to be $8/(9{\pi }^2)$ in both of these settings. Finally, for two-layer bipartite drawings, with straight edges between two parallel lines, we determine the midrange crossing constant to be $2/3$.

arXiv comment28 pages, 4 figures. It now includes the counter-example and lower bound for two-layer bipartite drawings