String graphs are quasi-isometric to planar graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911563351326720 |
|---|---|
| author | Davies, James |
| author_facet | Davies, James |
| contents | We prove that for every countable string graph $S$, there is a planar graph $G$ with $V(G)=V(S)$ such that \[ \frac{1}{23660800}d_S(u,v)
\le
d_G(u,v)
\le
162
d_S(u,v)
\] for all $u,v\in V(S)$, where $d_S(u,v)$, $d_G(u,v)$ denotes the distance between $u$ and $v$ in $S$ and $G$ respectively. In other words, string graphs are quasi-isometric to planar graphs.
This theorem lifts a number of theorems from planar graphs to string graphs, we give some examples. String graphs have Assouad-Nagata (and asymptotic dimension) at most 2. Connected, locally finite, quasi-transitive string graphs are accessible. A finitely generated group $Γ$ is virtually a free product of free and surface groups if and only if $Γ$ is quasi-isometric to a string graph.
Two further corollaries are that countable planar metric graphs and complete Riemannian planes are also quasi-isometric to planar graphs, which answers a question of Georgakopoulos and Papasoglu. For finite string graphs and planar metric graphs, our proofs yield polynomial time (for string graphs, this is in terms of the size of a representation given in the input) algorithms for generating such quasi-isometric planar graphs.
We further extend our techniques to show that every complete Riemannian surfaces $Σ$ of bounded Euler genus has a triangulation $G\subset Σ$ such that $G^{(1)} \hookrightarrow Σ$ is a quasi-isometry, where $G^{(1)}$ is the simplicial 1-skeleton of $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19602 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | String graphs are quasi-isometric to planar graphs Davies, James Combinatorics Discrete Mathematics Group Theory Geometric Topology Metric Geometry We prove that for every countable string graph $S$, there is a planar graph $G$ with $V(G)=V(S)$ such that \[ \frac{1}{23660800}d_S(u,v) \le d_G(u,v) \le 162 d_S(u,v) \] for all $u,v\in V(S)$, where $d_S(u,v)$, $d_G(u,v)$ denotes the distance between $u$ and $v$ in $S$ and $G$ respectively. In other words, string graphs are quasi-isometric to planar graphs. This theorem lifts a number of theorems from planar graphs to string graphs, we give some examples. String graphs have Assouad-Nagata (and asymptotic dimension) at most 2. Connected, locally finite, quasi-transitive string graphs are accessible. A finitely generated group $Γ$ is virtually a free product of free and surface groups if and only if $Γ$ is quasi-isometric to a string graph. Two further corollaries are that countable planar metric graphs and complete Riemannian planes are also quasi-isometric to planar graphs, which answers a question of Georgakopoulos and Papasoglu. For finite string graphs and planar metric graphs, our proofs yield polynomial time (for string graphs, this is in terms of the size of a representation given in the input) algorithms for generating such quasi-isometric planar graphs. We further extend our techniques to show that every complete Riemannian surfaces $Σ$ of bounded Euler genus has a triangulation $G\subset Σ$ such that $G^{(1)} \hookrightarrow Σ$ is a quasi-isometry, where $G^{(1)}$ is the simplicial 1-skeleton of $G$. |
| title | String graphs are quasi-isometric to planar graphs |
| topic | Combinatorics Discrete Mathematics Group Theory Geometric Topology Metric Geometry |
| url | https://arxiv.org/abs/2510.19602 |