Algorithms for Distance Problems in Continuous Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916648541224960 |
|---|---|
| author | Cabello, Sergio Garijo, Delia Kalb, Antonia Klute, Fabian Parada, Irene Silveira, Rodrigo I. |
| author_facet | Cabello, Sergio Garijo, Delia Kalb, Antonia Klute, Fabian Parada, Irene Silveira, Rodrigo I. |
| contents | We study the problem of computing the diameter and the mean distance of a continuous graph, i.e., a connected graph where all points along the edges, instead of only the vertices, must be taken into account. It is known that for continuous graphs with $m$ edges these values can be computed in roughly $O(m^2)$ time. In this paper, we use geometric techniques to obtain subquadratic time algorithms to compute the diameter and the mean distance of a continuous graph for two well-established classes of sparse graphs. We show that the diameter and the mean distance of a continuous graph of treewidth at most $k$ can be computed in $O(n\log^{O(k)} n)$ time, where $n$ is the number of vertices in the graph. We also show that computing the diameter and mean distance of a continuous planar graph with $n$ vertices and $F$ faces takes $O(n F \log n)$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_07769 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithms for Distance Problems in Continuous Graphs Cabello, Sergio Garijo, Delia Kalb, Antonia Klute, Fabian Parada, Irene Silveira, Rodrigo I. Computational Geometry Data Structures and Algorithms F.2 We study the problem of computing the diameter and the mean distance of a continuous graph, i.e., a connected graph where all points along the edges, instead of only the vertices, must be taken into account. It is known that for continuous graphs with $m$ edges these values can be computed in roughly $O(m^2)$ time. In this paper, we use geometric techniques to obtain subquadratic time algorithms to compute the diameter and the mean distance of a continuous graph for two well-established classes of sparse graphs. We show that the diameter and the mean distance of a continuous graph of treewidth at most $k$ can be computed in $O(n\log^{O(k)} n)$ time, where $n$ is the number of vertices in the graph. We also show that computing the diameter and mean distance of a continuous planar graph with $n$ vertices and $F$ faces takes $O(n F \log n)$ time. |
| title | Algorithms for Distance Problems in Continuous Graphs |
| topic | Computational Geometry Data Structures and Algorithms F.2 |
| url | https://arxiv.org/abs/2503.07769 |