Diameter Computation on (Random) Geometric Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908894245158912 |
|---|---|
| author | Bläsius, Thomas Schaub, Annemarie Wilhelm, Marcus |
| author_facet | Bläsius, Thomas Schaub, Annemarie Wilhelm, Marcus |
| contents | We present an algorithm that computes the diameter of random geometric graphs (RGGs) with expected average degree $Θ(n^δ)$ for constant $δ\in(0,1)$ in $\tilde{O}(n^{\frac{3}{2}(1+δ)} +n^{2 - \frac{5}{3}δ})$ time, asymptotically almost surely. This brings the running time down to $\tilde{O}(n^{\frac{33}{19}})\approx \tilde{O}(n^{1.737})$ for average degree $Θ(n^{3/19})$. To the best of our knowledge, this constitutes the first such bound for RGGs and for a substantial range of average degrees, it is notably smaller than the recent bound of $O^*(n^{2-1/18}) \approx O^*(n^{1.944})$ by Chan et al. (FOCS 2025) for the more general class of all unit disk graphs. Our algorithm also works on RGGs with the flat torus as ground space, with a running time in $\tilde{O}(n^{\frac{3}{2}(1+δ)} + n^{2 - \frac{1}{3}δ})$.
While our bounds on random geometric graphs are interesting in their own right, they are only an application of our main contribution: A general framework of deterministic graph properties that enable efficient diameter computation. Our properties are based on the existence of balanced separators that are well-behaved regarding the metric space defined by the graph and can be seen as a distillation of the combinatorial features a graph gets from having an underlying geometry.
As a by-product of verifying that RGGs fit into our framework, we also derive running time bounds for iFUB, a diameter algorithm by Crescenzi et al. (TCS 2013) that is highly efficient on real-world graphs. We show that a.a.s.\ iFUB achieves a speedup in $\tildeΩ(n^{δ/3})$ over the naive $O(nm)$ algorithm, but runs in $Ω(nm)$ time on torus RGGs. This constitutes the first theoretical analysis in a geometric setting and confirms prior empirical evidence, thus suggesting geometry as a reasonable model for certain real-world inputs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_16684 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Diameter Computation on (Random) Geometric Graphs Bläsius, Thomas Schaub, Annemarie Wilhelm, Marcus Data Structures and Algorithms We present an algorithm that computes the diameter of random geometric graphs (RGGs) with expected average degree $Θ(n^δ)$ for constant $δ\in(0,1)$ in $\tilde{O}(n^{\frac{3}{2}(1+δ)} +n^{2 - \frac{5}{3}δ})$ time, asymptotically almost surely. This brings the running time down to $\tilde{O}(n^{\frac{33}{19}})\approx \tilde{O}(n^{1.737})$ for average degree $Θ(n^{3/19})$. To the best of our knowledge, this constitutes the first such bound for RGGs and for a substantial range of average degrees, it is notably smaller than the recent bound of $O^*(n^{2-1/18}) \approx O^*(n^{1.944})$ by Chan et al. (FOCS 2025) for the more general class of all unit disk graphs. Our algorithm also works on RGGs with the flat torus as ground space, with a running time in $\tilde{O}(n^{\frac{3}{2}(1+δ)} + n^{2 - \frac{1}{3}δ})$. While our bounds on random geometric graphs are interesting in their own right, they are only an application of our main contribution: A general framework of deterministic graph properties that enable efficient diameter computation. Our properties are based on the existence of balanced separators that are well-behaved regarding the metric space defined by the graph and can be seen as a distillation of the combinatorial features a graph gets from having an underlying geometry. As a by-product of verifying that RGGs fit into our framework, we also derive running time bounds for iFUB, a diameter algorithm by Crescenzi et al. (TCS 2013) that is highly efficient on real-world graphs. We show that a.a.s.\ iFUB achieves a speedup in $\tildeΩ(n^{δ/3})$ over the naive $O(nm)$ algorithm, but runs in $Ω(nm)$ time on torus RGGs. This constitutes the first theoretical analysis in a geometric setting and confirms prior empirical evidence, thus suggesting geometry as a reasonable model for certain real-world inputs. |
| title | Diameter Computation on (Random) Geometric Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.16684 |