Skip to content
DraconiticResearch
Search Sources API
181,686 studies31 sourcesUpdated 4 min ago
PreprintCC BY 4.0arXiv

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

  • Hanna Döring
  • Kinga Nagy
Open at sourcePDFDOICite

Abstract

Consider a random geometric graph with vertices given by a Poisson point process, and whose edges depend on independent marks corresponding to the vertices and pairs of vertices. In this paper, we study two related questions on this general model: the number of edge crossings in a projection of this graph, and its graph-theoretical planarity. We focus on models with heavy-tailed mark distributions, in particular with polynomial tails with arbitrary exponents. We show that the asymptotic behaviour varies significantly depending on this exponent.

Related

  1. Integrals of general geometric random variables on the moduli space of hyperbolic surfaces
    Victor Le Guilloux
    HALPreprintCC BY 4.0Full textGeometry & topologyHALarXiv
  2. Detecting Random Geometric Graphs with General Kernel
    Dong Huang, Shuangping Li
    arXivPreprintarXiv licenceFull textProbabilityStatisticsarXiv
  3. Geometric (1+ε)-Spanners with Few Crossings
    Kelvin Luu, Csaba D. Tóth
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A linear bound for nested cycles without geometric crossings
    Jiangdong Ai, Gregory Gutin, Yiming Hao
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Geometric triangle-free graphs of large chromatic number
    István Tomon
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{doring2026planarity,
  title = {{Planarity and number of crossings in general models of random geometric graphs}},
  author = {Hanna Döring and Kinga Nagy},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08395},
  eprint = {2609.08395},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08395},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Planarity and number of crossings in general models of random geometric graphs
AU  - Hanna Döring
AU  - Kinga Nagy
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.08395
UR  - https://arxiv.org/abs/2609.08395
AB  - Consider a random geometric graph with vertices given by a Poisson point process, and whose edges depend on independent marks corresponding to the vertices and pairs of vertices. In this paper, we study two related questions on this general model: the number of edge crossings in a projection of this graph, and its graph-theoretical planarity. We focus on models with heavy-tailed mark distributions, in particular with polynomial tails with arbitrary exponents. We show that the asymptotic behaviour varies significantly depending on this exponent.
ER  -