pith. sign in

arxiv: 2605.16700 · v1 · pith:HWFRKB3Onew · submitted 2026-05-15 · 🧮 math.CO

Uniform Geodesic Drawings of Graphs

Saba Lepsveridze , Oriol Sol\'e-Pi This is my paper

Pith reviewed 2026-05-20 15:50 UTC · model grok-4.3

classification 🧮 math.CO
keywords crossing numbergeodesic drawingunit sphereconvex domainsmoothing argumentmidrange crossing constantuniform distributionmeasurable edge set
0
0 comments X

The pith

Among measurable edge arrangements of fixed density on the sphere, crossings are minimized by connecting points within a fixed distance threshold.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that in a continuous model where vertices are spread uniformly on the sphere, the total crossings in a dense drawing reach their lowest value when edges are drawn only between points that lie no farther apart than some chosen threshold distance. This same minimization holds for straight-line edges inside a convex region in the plane. A smoothing procedure then carries the continuous lower bound over to ordinary finite graphs whose vertices are placed uniformly, and in the low-density regime this recovers the conjectured numerical constant 8/(9π²) for the midrange crossing number.

Core claim

Among all measurable edge arrangements of a fixed density on the unit sphere, the amount of crossings is minimized by the arrangement that connects pairs of points within a fixed distance threshold. The same holds for straight-line drawings inside convex planar domains. These continuous minimization statements are transferred to finite graphs by a smoothing argument that preserves sharpness, yielding in the small-density limit the conjectured lower bound of 8/(9π²) on the midrange crossing constant for this restricted model.

What carries the argument

The threshold-distance connection rule for measurable edge sets of fixed density, which is shown to be the crossing minimizer in the continuous geodesic setting on the sphere.

If this is right

  • The crossing number of any dense uniform drawing on the sphere is at least as large as that of the corresponding threshold-distance drawing.
  • In the small-density limit the midrange crossing constant is bounded below by 8/(9π²) for graphs drawn with geodesic edges.
  • An identical minimization statement holds for straight-line drawings whose vertices are uniform inside a compact convex planar domain.
  • The smoothing step produces finite-graph bounds that remain sharp when the density tends to zero.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The continuous formulation may supply new lower bounds for crossing numbers on other surfaces equipped with uniform measures.
  • Numerical optimization of edge sets in the continuous model could be used to test the sharpness of the bound for moderate densities.
  • The planar analogue suggests that similar threshold rules might minimize crossings for uniform point sets inside non-convex regions as well.

Load-bearing premise

The smoothing argument transfers the continuous minimization result to finite graphs while preserving sharpness of the bound, especially in the small density limit.

What would settle it

An explicit measurable edge set of fixed density on the sphere whose total crossings fall below those of the threshold-distance arrangement would falsify the claimed minimization.

Figures

Figures reproduced from arXiv: 2605.16700 by Oriol Sol\'e-Pi, Saba Lepsveridze.

Figure 1
Figure 1. Figure 1: Two streams of edges at a crossing point x. The two strips overlap in a parallelogram, and the area element of this parallelogram gives the factor |sin(θ1 − θ2)|. Observe that the spherical cap of radius t has normalized area precisely (1 − cost)/2, which corresponds to average degree or ordered edge density above. We now collect the notation and technical lemmas required for the proof. We parametrize cros… view at source ↗
Figure 2
Figure 2. Figure 2: Curves [x1x2] and [x3x4] are non-crossing, but they begin to cross after a small perturbation. Observe that the endpoint x2 is close to the edge [x3x4]. To see this, compare the supporting great circles. If n = (x×x ′ )/ |x × x ′ | and n ′ = (y ×y ′ )/ |y × y ′ | are unit normals, then |x × x ′ | = sin d(x, x′ ) ≥ sin α ≥ cα. On the other hand, by linearity, the cross product changes by at most O(δ). Thus,… view at source ↗
read the original 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\pi^2)$ for this restricted model.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proves a sharp inequality for weighted geodesic drawings on S² in a continuous setting: among all measurable edge arrangements of a fixed density, the crossing measure is minimized by connecting pairs of points within a fixed distance threshold. It establishes an analogous result for straight-line drawings in convex planar domains. These continuous minimization results are transferred to finite n-vertex graphs with uniformly distributed vertices via a smoothing argument, recovering the conjectured lower bound of 8/(9π²) on the midrange crossing constant in the small-density limit.

Significance. If the continuous minimization and the transfer both hold with the claimed sharpness, the work would supply a rigorous analytic foundation for a long-standing conjecture on crossing numbers of dense uniform geometric graphs, bridging measure-theoretic optimization on manifolds with discrete graph drawing problems. The parameter-free character of the continuous bound and the explicit recovery of the numerical constant are notable strengths.

major comments (1)
  1. [transfer from continuous to discrete (smoothing argument)] The smoothing argument that transfers the continuous threshold-minimizer to finite uniform graphs (the step that recovers the exact constant 8/(9π²) as density → 0) requires explicit error estimates showing that the crossing-density discrepancy vanishes uniformly in the double limit n → ∞ and density → 0. Without such estimates, it is unclear whether o(1) discrepancies introduced by smoothing the discrete drawing to a measurable one (or vice versa) remain negligible for the extremal threshold configurations.
minor comments (2)
  1. Define 'measurable edge arrangements' and 'weighted geodesic drawings' with precise measure-theoretic language in the introduction or preliminary section to avoid ambiguity when stating the continuous minimization result.
  2. Clarify the precise sense in which the recovered constant 8/(9π²) is 'conjectured' versus 'proved' for the restricted model of uniform geodesic drawings.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the importance of rigorous error control in the smoothing step. We address the major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [transfer from continuous to discrete (smoothing argument)] The smoothing argument that transfers the continuous threshold-minimizer to finite uniform graphs (the step that recovers the exact constant 8/(9π²) as density → 0) requires explicit error estimates showing that the crossing-density discrepancy vanishes uniformly in the double limit n → ∞ and density → 0. Without such estimates, it is unclear whether o(1) discrepancies introduced by smoothing the discrete drawing to a measurable one (or vice versa) remain negligible for the extremal threshold configurations.

    Authors: We agree that the current outline of the smoothing argument would be strengthened by explicit quantitative bounds that control the discrepancy uniformly in the double limit. Section 4 currently shows that, for any fixed density ρ>0, the normalized crossing number of the n-vertex uniform geometric graph converges in probability to the continuous crossing measure of the threshold drawing as n→∞. To pass to the joint limit ρ→0, we will add a new lemma establishing that the total discrepancy between the discrete edge measure and its smoothed continuous counterpart is bounded by O(ρ + n^{-1/2}) uniformly over all threshold configurations. This bound vanishes whenever ρ→0 slower than n^{-1/2}, which is the regime needed to recover the exact constant 8/(9π²). The revised manuscript will contain the full proof of this error estimate together with a statement of the resulting asymptotic lower bound. revision: yes

Circularity Check

0 steps flagged

No significant circularity; continuous minimization and smoothing transfer are independent of the target bound

full rationale

The derivation begins with a measure-theoretic comparison among measurable edge arrangements of fixed density on S², establishing that threshold geodesic connections minimize crossings. This continuous result is proved directly from the geometry of the sphere and crossing measure definitions without reference to finite graphs or the specific constant 8/(9π²). The subsequent smoothing argument approximates discrete uniform drawings by measurable ones (and conversely) to transfer the inequality, with the constant recovered only in the double limit as density tends to zero. No equation reduces the discrete claim to a fitted parameter or self-referential definition, and the smoothing step is presented as an approximation technique whose error control is argued separately. No load-bearing self-citation or ansatz smuggling is required for the core inequality.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard measure theory for defining densities and arrangements, plus the domain-specific properties of geodesics and Euclidean distances. No free parameters are fitted; the threshold emerges from the fixed-density constraint. No new entities are postulated.

axioms (2)
  • standard math Standard axioms of Lebesgue measure and integration on manifolds
    Invoked to define measurable edge arrangements of fixed density on the sphere and plane.
  • domain assumption Geodesic distance is the shortest path on the sphere; Euclidean distance applies in the plane
    Used to define the drawings and the threshold connection rule.

pith-pipeline@v0.9.0 · 5633 in / 1416 out tokens · 64277 ms · 2026-05-20T15:50:14.998018+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    On topological graphs with at most four crossings per edge.Comput

    Eyal Ackerman. On topological graphs with at most four crossings per edge.Comput. Geom., 85:101574, 31, 2019

    work page 2019

  2. [2]

    Ajtai, V

    M. Ajtai, V. Chvátal, M. M. Newborn, and E. Szemerédi. Crossing-free subgraphs. InTheory and practice of combinatorics, volume 60 ofNorth-Holland Math. Stud., pages 9–12. North-Holland, Amsterdam, 1982

    work page 1982

  3. [3]

    Closing in on Hill’s conjecture.SIAM J

    József Balogh, Bernard Lidický, and Gelasio Salazar. Closing in on Hill’s conjecture.SIAM J. Discrete Math., 33(3):1261–1276, 2019

    work page 2019

  4. [4]

    Improving the Crossing Lemma by characterizing dense 2-planar and 3-planar graphs

    Aaron Büngener and Michael Kaufmann. Improving the Crossing Lemma by characterizing dense 2-planar and 3-planar graphs. In32nd International Symposium on Graph Drawing and Network Visualization, volume 320 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 29, 22. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024

    work page 2024

  5. [5]

    Volume in terms of concurrent cross-sections.Pacific J

    Herbert Busemann. Volume in terms of concurrent cross-sections.Pacific J. Math., 3:1–12, 1953

    work page 1953

  6. [6]

    Some remarks on the midrange crossing constant

    Éva Czabarka, Inne Singgih, László Székely, and Zhiyu Wang. Some remarks on the midrange crossing constant. Studia Sci. Math. Hungar., 57(2):187–192, 2020

    work page 2020

  7. [7]

    T. K. Dey. Improved bounds for planark-sets and related problems.Discrete Comput. Geom., 19(3):373–382,

    work page

  8. [8]

    Dedicated to the memory of Paul Erdős

    work page

  9. [9]

    Erdős and R

    P. Erdős and R. K. Guy. Crossing number problems.Amer. Math. Monthly, 80:52–58, 1973

    work page 1973

  10. [10]

    New lower bound techniques for vlsi.Mathematical Systems Theory, 17(1):47–70, 1984

    Frank Thomson Leighton. New lower bound techniques for vlsi.Mathematical Systems Theory, 17(1):47–70, 1984

    work page 1984

  11. [11]

    Improving the crossing lemma by finding more crossings in sparse graphs.Discrete Comput

    János Pach, Radoˇ s Radoiˇ cić, Gábor Tardos, and Géza Tóth. Improving the crossing lemma by finding more crossings in sparse graphs.Discrete Comput. Geom., 36(4):527–552, 2006

    work page 2006

  12. [12]

    New bounds on crossing numbers

    János Pach, Joel Spencer, and Géza Tóth. New bounds on crossing numbers. InProceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), pages 124–133. ACM, New York, 1999

    work page 1999

  13. [13]

    Graphs drawn with few crossings per edge.Combinatorica, 17(3):427–439, 1997

    János Pach and Géza Tóth. Graphs drawn with few crossings per edge.Combinatorica, 17(3):427–439, 1997

    work page 1997

  14. [14]

    The graph crossing number and its variants: a survey.Electron

    Marcus Schaefer. The graph crossing number and its variants: a survey.Electron. J. Combin., DS21:90, 2013

    work page 2013

  15. [15]

    László A. Székely. Crossing numbers and hard Erdős problems in discrete geometry.Combin. Probab. Comput., 6(3):353–358, 1997. Department of Mathematics, Massachusetts Institute of Technology Email address:sabal@mit.edu Department of Mathematics, Massachusetts Institute of Technology Email address:oriolsp@mit.edu

    work page 1997