String graphs are quasi-isometric to planar graphs
James Davies
我们证明,对于每个可计数的字符串图 S,有一个带有 V(G)=V(S) 的平面图 G,使得 1/23660800d_S(u,v) ≤ d_G(u,v) ≤ 162 d_S(u,v) ≤ 162 d_S(u,v) 的 u,v ,其中 d_S(u,v), d_G(u,v) 表示 u 和 v 之间的距离。 换句话说,字符串图形是准等距平面图。 这个定理从平面图提升到弦图,我们举了一些例子。 字符串图形最多有Assouad-Nagata(和渐近尺寸)。 连接的,本地有限,准瞬态字符串图是可访问的。 有限生成的组 Γ 实际上是自由和表面组的自由产品,如果并且只有在 Γ 准对字符串图时。 另外两个推论是,可计数平面公制图和完整的黎曼平面平面图也是与平面图的准等距图,它回答了Georgakopoulos和Papasoglu的问题。 对于有限字符串图形和平面公制图,我们的证明产生多项式时间(对于字符串图形,这是以输入中给出的表示的大小而言)算法用于生成这种准等距平面图。
We prove that for every countable string graph S, there is a planar graph G with V(G)=V(S) such that 1/23660800d_S(u,v) ≤ d_G(u,v) ≤ 162 d_S(u,v) for all u,v∈ 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. Connecte...
