Thomas Bläsius

Thomas Bläsius, Emil Dohse, Deborah Haun et al.

Hyperbolic uniform disk graphs (HUDGs) are intersection graphs of disks with some radius $r$ in the hyperbolic plane, where $r$ may be constant or depend on the number of vertices in a family of HUDGs. We show that HUDGs with constant clique number do not admit \emph{product structure}, i.e., that there is no constant $c$ such that every such graph is a subgraph of $H \boxtimes P$ for some graph $H$ of treewidth at most $c$. This justifies that HUDGs are described as not having a grid-like structure in the literature, and is in contrast to unit disk graphs in the Euclidean plane, whose grid-like structure is evident from the fact that they are subgraphs of the strong product of two paths and a clique of constant size [Dvořák et al., '21, MATRIX Annals]. By allowing $H$ to be any graph of constant treewidth instead of a path-like graph, we reject the possibility of a grid-like structure not merely by the maximum degree (which is unbounded for HUDGs) but due to their global structure. We complement this by showing that for every (sub-)constant $r$, HUDGs admit product structure, whereas the typical hyperbolic behavior is observed if $r$ grows with the number of vertices. Our proof involves a family of $n$-vertex HUDGs with radius $\log n$ that has bounded clique number but unbounded treewidth, and one for which the ratio of treewidth and clique number is $\log n / \log \log n$. Up to a $\log \log n$ factor, this negatively answers a question raised by Bläsius et al. [SoCG '25] asking whether balanced separators of HUDGs with radius $\log n$ can be covered by less than $\log n$ cliques. Our results also imply that the local and layered tree-independence number of HUDGs are both unbounded, answering an open question of Dallard et al. [arXiv '25].

Thomas Bläsius, Annemarie Schaub, Marcus Wilhelm

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.