A WSPD, Separator and Small Tree Cover for c-packed Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913831708524544 |
|---|---|
| author | Deryckere, Lindsey Gudmundsson, Joachim van Renssen, André Sha, Yuan Wong, Sampson |
| author_facet | Deryckere, Lindsey Gudmundsson, Joachim van Renssen, André Sha, Yuan Wong, Sampson |
| contents | The $c$-packedness property, proposed in 2010, is a geometric property that captures the spatial distribution of a set of edges. Despite the recent interest in $c$-packedness, its utility has so far been limited to Fréchet distance problems. An open problem is whether a wider variety of algorithmic and data structure problems can be solved efficiently under the $c$-packedness assumption, and more specifically, on $c$-packed graphs.
In this paper, we prove two fundamental properties of $c$-packed graphs: that there exists a linear-size well-separated pair decomposition under the graph metric, and there exists a constant size balanced separator. We then apply these fundamental properties to obtain a small tree cover for the metric space and distance oracles under the shortest path metric. In particular, we obtain a tree cover of constant size, an exact distance oracle of near-linear size and an approximate distance oracle of linear size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_06884 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A WSPD, Separator and Small Tree Cover for c-packed Graphs Deryckere, Lindsey Gudmundsson, Joachim van Renssen, André Sha, Yuan Wong, Sampson Computational Geometry The $c$-packedness property, proposed in 2010, is a geometric property that captures the spatial distribution of a set of edges. Despite the recent interest in $c$-packedness, its utility has so far been limited to Fréchet distance problems. An open problem is whether a wider variety of algorithmic and data structure problems can be solved efficiently under the $c$-packedness assumption, and more specifically, on $c$-packed graphs. In this paper, we prove two fundamental properties of $c$-packed graphs: that there exists a linear-size well-separated pair decomposition under the graph metric, and there exists a constant size balanced separator. We then apply these fundamental properties to obtain a small tree cover for the metric space and distance oracles under the shortest path metric. In particular, we obtain a tree cover of constant size, an exact distance oracle of near-linear size and an approximate distance oracle of linear size. |
| title | A WSPD, Separator and Small Tree Cover for c-packed Graphs |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2505.06884 |