Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.09620 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909687269556224 |
|---|---|
| author | Li, George Z. Tan, Zihan Zhang, Tianyi |
| author_facet | Li, George Z. Tan, Zihan Zhang, Tianyi |
| contents | We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with $k$ terminals, the goal is to construct an emulator, which is a smaller edge-weighted planar graph that contains the terminals and exactly preserves the pairwise distances between them. We construct exact planar emulators of size $O(f^2k^2)$ in the setting where terminals lie on $f$ faces in the planar embedding of the input graph. Our result generalizes and interpolates between the previous results of Chang and Ophelders and Goranci, Henzinger, and Peng which is an $O(k^2)$ bound in the setting where all terminals lie on a single face (i.e., $f=1$), and the result of Krauthgamer, Nguyen, and Zondiner, which is an $O(k^4)$ bound for the general case (i.e., $f=k$).
Our construction follows a recent new way of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09620 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Paths and Intersections: Exact Emulators for Planar Graphs Li, George Z. Tan, Zihan Zhang, Tianyi Data Structures and Algorithms Combinatorics We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with $k$ terminals, the goal is to construct an emulator, which is a smaller edge-weighted planar graph that contains the terminals and exactly preserves the pairwise distances between them. We construct exact planar emulators of size $O(f^2k^2)$ in the setting where terminals lie on $f$ faces in the planar embedding of the input graph. Our result generalizes and interpolates between the previous results of Chang and Ophelders and Goranci, Henzinger, and Peng which is an $O(k^2)$ bound in the setting where all terminals lie on a single face (i.e., $f=1$), and the result of Krauthgamer, Nguyen, and Zondiner, which is an $O(k^4)$ bound for the general case (i.e., $f=k$). Our construction follows a recent new way of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest. |
| title | Paths and Intersections: Exact Emulators for Planar Graphs |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2507.09620 |