O(1)-Distortion Planar Emulators for String Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915574780526592 |
|---|---|
| author | Chang, Hsien-Chih Conroy, Jonathan Tan, Zihan Zheng, Da Wei |
| author_facet | Chang, Hsien-Chih Conroy, Jonathan Tan, Zihan Zheng, Da Wei |
| contents | 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) \le δ_H(u,v) \le O(1) \cdot δ_G(u,v).$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21700 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | O(1)-Distortion Planar Emulators for String Graphs Chang, Hsien-Chih Conroy, Jonathan Tan, Zihan Zheng, Da Wei Data Structures and Algorithms Computational Geometry Discrete Mathematics Combinatorics Metric Geometry 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) \le δ_H(u,v) \le O(1) \cdot δ_G(u,v).$ |
| title | O(1)-Distortion Planar Emulators for String Graphs |
| topic | Data Structures and Algorithms Computational Geometry Discrete Mathematics Combinatorics Metric Geometry |
| url | https://arxiv.org/abs/2510.21700 |