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 $\Gamma$ is virtually a free product of free and surface groups if and only if $\Gamma$ 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.
翻译:我们证明,对于任意可数弦图$S$,存在一个平面图$G$满足$V(G)=V(S)$,使得对所有$u,v\in V(S)$,有\[ \frac{1}{23660800}d_S(u,v) \le d_G(u,v) \le 162 d_S(u,v) \]成立,其中$d_S(u,v)$和$d_G(u,v)$分别表示$u$与$v$在$S$和$G$中的距离。换言之,弦图拟等距于平面图。该定理将一系列关于平面图的结论推广至弦图,我们给出若干示例。弦图的Assouad-Nagata维数(及渐近维数)至多为2。连通的、局部有限的、拟传递的弦图是可访问的。一个有限生成群$\Gamma$是自由群与曲面群的自由积的虚拟群,当且仅当$\Gamma$拟等距于一个弦图。进一步得到两个推论:可数平面度量图与完备黎曼平面也拟等距于平面图,这回答了Georgakopoulos与Papasoglu提出的一个问题。对于有限弦图与平面度量图,我们的证明可生成多项式时间算法(对弦图而言,该算法复杂度以输入给定的表示规模为参数)来构造此类拟等距的平面图。