Planarity and number of crossings in general models of random geometric graphs

Scientific Impact Assessment

Core Contribution. This is a theoretical stochastic-geometry paper that generalizes two previously separate lines of work — the number of edge crossings in projections of the Gilbert graph (Chimani–Döring–Reitzner; Döring–de Jonge) and the graph-theoretic planarity of hard random geometric graphs (Biniaz et al.) — to a much broader class of marked random geometric graphs. In these general models, edges depend on i.i.d. vertex marks and edge marks through a connection function φ, subsuming the random connection model, soft RGGs, and Boolean/max-kernel models. The headline results are: (i) a general two-sided bound and precise asymptotic (Theorem A/6.1) for the expected number of crossings in any such model, expressed through the connection probability g(x); (ii) a detailed variance analysis catalogued by geometric "configurations" (Section 6.2); and (iii) planarity thresholds and complete/bipartite-subgraph count asymptotics for three concrete heavy-tailed (Pareto, exponent α) models. The conceptually interesting finding is that behaviour changes qualitatively with the tail exponent: for light-enough tails planarity is governed by non-existence of a K₅ (as in the Gilbert graph), while for heavier tails the smallest non-planar obstruction can be a subgraph whose vertex count grows with t, or a K₃,₃ — a genuinely new qualitative regime.

Methodological Rigor. The paper is technically careful. It uses standard but non-trivial machinery (Slivnyak–Mecke formula, second-moment method, integral geometry) alongside a notable methodological device: an induction "at the level of functions," building subgraphs vertex-by-vertex while tracking a parameter that caps maximal edge length/mark. This lets the authors derive matching upper and lower bounds for otherwise intractable subgraph counts in heavy-tailed regimes where expectations are distorted by rare large marks. A telling sign of care is that they identify and correct a constant error (a missing exponent) in the prior published result [3]. The proofs are internally consistent and the two-sided bounds are honest about where they are and are not sharp. Rigor is a clear strength.

Potential Impact. The audience is the stochastic-geometry / random-geometric-graph community, plus adjacent workers on scale-free percolation and spatial network models (Gracar–Grauer–Mörters and related). Theorem A is a reusable building block: it reduces the expected crossing count for *any* marked model to an integral of the connection function, which future authors can plug into. The configuration-based variance toolkit is likewise a resource others can adapt. However, the topic — crossing numbers and planarity of RGGs — is a specialized corner of the field, and the practical/applied consequences (e.g., graph-drawing, network layout stress) are indirect. This is foundational-within-a-niche rather than field-changing.

Timeliness & Relevance. Heavy-tailed, long-edge geometric graphs are an active area because they model scale-free spatial networks. The paper explicitly notes that existing results on polynomial tails restrict to α > d (where geometric localization tools apply), and it deliberately pushes to arbitrary exponents. This addresses a real gap and connects to a live research thread, giving it good relevance within its community.

Strengths & Limitations. Strengths: (1) genuine generality of the expected-crossings result; (2) a clean and reusable inductive technique for heavy-tailed subgraph counts; (3) comprehensive, systematic treatment across three models and two questions; (4) careful correction of prior literature; (5) illuminating conceptual observations (e.g., the SRGG interpolating between Erdős–Rényi and Gilbert behaviour depending on α). Limitations: (1) several planarity thresholds are non-sharp — the authors are candid that finding existence results for high-order subgraphs is hard and that a sharp phase transition is unclear; (2) the variance results are not consolidated into a single theorem, requiring the reader to assemble configurations; (3) the first two moments are explicitly shown to be uninformative about the distribution of X_t in some regimes, and the authors decline to resolve the harder distributional questions there; (4) the paper is dense and notation-heavy, limiting accessibility outside specialists. There is no empirical/computational component (appropriate for the subject, but it means no distributional simulations to complement the moment analysis).

Other observations. The work is essentially reproducible by a competent probabilist from the text alone (all proofs are given), so "reproducibility" in the empirical sense does not apply. The refutation/replication content is modest but real: it independently reconfirms the Biniaz et al. planarity threshold and the Gilbert-graph crossing asymptotics while fixing a constant. The barrier to entry to *extend* this work is low in resources (pen-and-paper) but high in required expertise. Overall this is a solid, rigorous, incremental-but-substantive contribution that will be cited and built upon by a modest slice of the stochastic-geometry subfield, without reaching beyond it.