Uniform Geodesic Drawings of Graphs
Saba Lepsveridze, Oriol Solé-Pi · 2026
Read Uniform Geodesic Drawings of Graphs by Saba Lepsveridze, Oriol Solé-Pi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16700.txt.
Introduction
Lepsveridze and Solé-Pi ask how few crossings a dense drawing can achieve when vertices spread uniformly across a compact convex planar domain or over the unit sphere. For weighted geodesic drawings on the sphere, they prove a sharp inequality. Among fixed-density edge arrangements, crossings are minimized by connecting pairs within a fixed distance threshold. A planar analogue covers straight-line drawings in convex domains. Smoothing transfers these results to finite graphs, recovering a conjectured midrange crossing-constant lower bound in the small-density limit.
Catalog record
| CREATOR | Saba Lepsveridze, Oriol Solé-Pi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50961 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.16700
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Uniform Geodesic Drawings of Graphs Saba Lepsveridze, Oriol Solé-Pi 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 𝕊 2 \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 π 2 ) 8/(9\pi^{2}) for this restricted model. 1. Introduction A drawing of a graph G is a representation of the graph on either \mathbb{R}^{2} or \mathbb{S}^{2} in which the vertices are represented by distinct points and the edges by continuous simple curves connecting their respective endpoints. A drawing is called good if no edge contains a vertex in its relative interior, no two edges are tangent to each other or intersect at infinitely many points, and no three edges share an interior point. A crossing is a point which lies at the intersection of two edges but does not represent a vertex. The crossing number of G is the least possible number of crossings across all good drawings of G , and we denote it by \mathrm{cr}(G) . Moreover, given a good drawing \mathcal{D} of a graph, we write \operatorname{cr}({\mathcal{D}}) for the number of crossings induced by \mathcal{D} . By performing a stereographic projection, it can be seen that the definition of \mathrm{cr}(G) does not depend on whether we consider drawings on \mathbb{R}^{2} or \mathbb{S}^{2} . We shall work exclusively with simple graphs. 1.1. The midrange crossing constant and our work The celebrated Crossing Lemma, proved independently by Ajtai et al. [ 2 ] and Leighton [ 9 ] , states that if m\geq 4n then any graph G with n vertices and m edges must satisfy (1) \mathrm{cr}(G)\geq\frac{m^{3}}{64n^{2}}\,. This bound, apart from being a foundational result in the study of crossing numbers, can be used to prove several other remarkable results, including the Szemerédi–Trotter Theorem [ 14 ] from incidence geometry, and the currently best known upper bounds for the Erdős unit distance problem [ 14 ] and the number of k -edges produced by planar point sets [ 7 ] . For positive integers n and m , we write \kappa(n,m) to denote the least crossing number among graphs with n vertices and m edges. In 1973, Erdős and Guy [ 8 ] conjectured that along any sequence of pairs of the form (n,m) with n and m/n both approaching infinity, the limit of \kappa(n,m){n^{2}}/{m^{3}} exists (and this limit is independent of the sequence being used). As it turns out, this is not quite correct, but it becomes true after adding also the assumption that n^{2}/m approaches infinity. Theorem 1 (Pach, Spencer, Tóth [ 11 ] ) . If n\ll m\ll n^{2} , then the limit \lim_{n\rightarrow\infty}\kappa(n,m)\frac{n^{2}}{m^{3}}=\kappa>0 exists. Pach, Spencer and Tóth called this constant \kappa the midrange crossing constant . The inequality ( 1 ) gives the lower bound \kappa\geq 1/64 . There is a long and ongoing line of research [ 12 , 10 , 1 , 4 ] which aims at improving this lower bound. The best known result in this direction, due to Büngener and Kaufmann [ 4 ] , tells us that \kappa\geq\frac{1500}{41209}\approx\frac{1}{27.48} . On the other hand, the best known constructions suggest the value (2) \kappa=\frac{8}{9\pi^{2}}\,. Pach and Tóth [ 12 , 10 ] showed that \kappa is bounded from above by this constant by considering graphs drawn on the plane as follows: take a small perturbation of the \sqrt{n}\times\sqrt{n} grid and connect by a segments any two vertices at distance at most the suitable threshold t . Czabarka, Singgih, Székely and Wang [ 6 ] later gave a clean verification of the same upper bound using drawings on the sphere where the vertices are distributed uniformly and nearby vertices are connected via spherical geodesics. As our main contribution, we obtain a partial converse of this result. More precisely, we show that among all geodesic drawings of dense graphs with “uniform” vertex sets, the threshold constructions are indeed asymptotically optimal. We will define this notion of uniformity and state our main theorems more precisely in the next subsection. For now, we state a continuous version of our main theorems, which show the essence of our results. Theorem 2 . Let \Omega\subset{\mathbb{R}}^{2} be a compact convex set. Let w:\Omega\times\Omega\to[0,1] be arbitrary symmetric function. Let random points x_{1},x_{2},x_{3},x_{4}\in\Omega be sampled independently and uniformly. Then, {\mathbb{E}}\Bigl[{w(x_{1},x_{2})w(x_{3},x_{4})\mathbf{1}{\{[x_{1}x_{2}]\text{ crosses }[x_{3}x_{4}]\}}\Bigr]}\geq\frac{8}{9\pi^{2}}\,{\mathbb{E}}[w(x_{1},x_{2})]^{3}\,, where [xy] denotes the segment with endpoints x and y . Theorem 3 . Suppose w:{\mathbb{S}}^{2}\times{\mathbb{S}}^{2}\to[0,1] is arbitrary symmetric measurable function. Let random points x_{1},x_{2},x_{3},x_{4}\in{\mathbb{S}}^{2} be sampled independently and uniformly. Then, {\mathbb{E}}\Bigl[{w(x_{1},x_{2})w(x_{3},x_{4})\mathbf{1}{\{[x_{1}x_{2}]\text{ crosses }[x_{3}x_{4}]\}}\Bigr]}\geq\frac{(\sin t-t\cos t)^{2}}{8\pi^{2}}\,, where t\in[0,\pi] satisfies \cos t=1-2{\mathbb{E}}[w(x_{1},x_{2})] . Equality is attained by w(x,y):=\mathbf{1}{\{d(x,y)\leq t\}}. Here, [xy] denotes the short geodesic arc connecting x and y , and d(x,y) the length of this arc. Observe that in the spherical setting, when the edge density approaches 0 , the lower bound constant tends precisely to 8/(9\pi^{2}) . This does not imply a lower bound for \kappa , as we are working with a restricted class of drawings. However, to the best of our knowledge, this is the first non-trivial class of drawings of dense graphs where we are able to prove sharp asymptotic results as the density approaches 0. We are optimistic that our techniques, in combination with additional ideas, might lead to a full proof of a matching \kappa\geq{8}/{(9\pi^{2})} lower bound. 1.2. Main theorems We shall work exclusively with spherical geodesic drawings and planar straight-line drawings, defined below. Definition 1 (Spherical geodesic drawings and straight-line drawings) . A spherical geodesic drawing of a graph G=(V,E) is a good drawing where the vertices are represented using an injective map p:V\longrightarrow{\mathbb{S}}^{2} such that no adjacent pair is mapped to antipodal points, and each edge uv\in E is drawn as the shorter geodesic segment [p(u)p(v)] . Similarly, a straight-line drawing of G is a good drawing where the vertices are represented using an injective map p:V\to\mathbb{R}^{2} , and the edges are drawn as segments. Note that spherical geodesic drawings and straight-line drawings are completely determined by their defining map p , and thus we denote them simply by {\mathcal{D}}=(G,p) . Definition 2 (Uniform spherical geodesic drawing sequence) . Let {\mathcal{D}}_{n}=(G_{n},p_{n}) be spherical geodesic drawings with |V(G_{n})|=n . The sequence \{{\mathcal{D}}_{n}\} is uniform on the sphere if \nu_{n}:=\frac{1}{n}\sum_{v\in V(G_{n})}\delta_{p_{n}(v)}\quad\Longrightarrow\quad\mu:=\frac{\sigma}{4\pi} weakly as probability measures on {\mathbb{S}}^{2} . Here \sigma denotes spherical area measure. Equivalently, for every continuous F:{\mathbb{S}}^{2}\to{\mathbb{R}} , \frac{1}{n}\sum_{v\in V(G_{n})}F(p_{n}(v))\longrightarrow\int_{{\mathbb{S}}^{2}}F\,\mathrm{d}\mu\,. Definition 3 (Uniform planar straight-line drawing sequence) . Let \Omega\subset{\mathbb{R}}^{2} be a compact convex set with nonempty interior, and let \lambda:=\frac{1}{\operatorname{area}(\Omega)}\,\mathcal{L}^{2}\big|_{\Omega} be the normalized area measure on \Omega (i.e. the uniform probability measure on \Omega ). A sequence of straight-line drawings {\mathcal{D}}_{n}=(G_{n},p_{n}) with |V(G_{n})|=n is uniform in \Omega if \frac{1}{n}\sum_{v\in V(G_{n})}\delta_{p_{n}(v)}\quad\Longrightarrow\quad\lambda weakly. Equivalently, the averages of every continuous test function on \Omega over the