O(1)-用于字符串图形的扭曲平面模拟器
O(1)-Distortion Planar Emulators for String Graphs
Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, Da Wei Zheng
arXiv
2025年10月24日
我们显示每个未加权的字符串图 G 都有 O(1)- 失真平面模拟器:即存在一个(边缘加权)平面图 H 与 V(H) = V(G),使每对顶点 (u,v) 满足 δ_G(u,v) ≤δ_H(u,v) ≤ O(1) ·δ_G(u,v,v)。
We show that every unweighted string graph G has an O(1)-distortion planar emulator: that is, there exists an (edge-weighted) planar graph H with V(H) = V(G), such that every pair of vertices (u,v) satisfies δ_G(u,v) ≤δ_H(u,v) ≤ O(1) ·δ_G(u,v).