Paths and Intersections: Exact Emulators for Planar Graphs

George Z. Li, Zihan Tan, Tianyi Zhang · 2025

Read Paths and Intersections: Exact Emulators for Planar Graphs by George Z. Li, Zihan Tan, Tianyi Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-09620.txt.

Introduction

George Li, Zihan Tan, and Tianyi Zhang study how to shrink planar graphs while keeping distances exact in a 2025 math paper. A planar graph can be drawn without crossing edges. Given a set of key points called terminals, the goal is a smaller graph that still gives the exact distance between every pair of terminals.

The authors build such stand-in graphs whose size depends on how many faces of the drawing hold terminals. Their bound smoothly connects two known cases: a tight bound when all terminals sit on one face, and a looser one for the general case. The construction views the graph as a web of paths and crossings. The authors suggest that viewpoint may help with other graph problems too.

Catalog record

CREATORGeorge Z. Li, Zihan Tan, Tianyi Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE109 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-09620

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Paths and Intersections: Exact Emulators for Planar Graphs George Z. Li, Zihan Tan, Tianyi Zhang Abstract We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with k 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 2 ​ k 2 ) O(f^{2}k^{2}) in the setting where terminals lie on f 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 ) O(k^{2}) bound in the setting where all terminals lie on a single face (i.e., f = 1 f=1 ), and the result of Krauthgamer, Nguyen, and Zondiner, which is an O ⁡ ( k 4 ) O(k^{4}) bound for the general case (i.e., f = k 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. 1 Introduction Graph compression is an approach that reduces the size of large graphs while preserving key properties, such as flow/cut/distance information. By shrinking the graph before performing computations, it saves computational resources. This approach has played a crucial role in designing faster and more efficient graph algorithms. We study a specific type of graph compression, called vertex sparsifiers for preserving distances , on planar graphs. The input is an edge-weighted planar graph G and a subset T\subseteq V(G) of its vertices called terminals . The goal is to compute a smaller planar graph H that contains all terminals in T and preserves their pairwise distances in G . Such a graph H is called an emulator of G . Formally, H is a quality- q emulator of G with respect to T , for some real number q\geq 1 , iff \forall t,t^{\prime}\in T,\quad\textnormal{{dist}}_{G}(t,t^{\prime})\leq\textnormal{{dist}}_{H}(t,t^{\prime})\leq q\cdot\textnormal{{dist}}_{G}(t,t^{\prime}). The research focus in vertex sparsification lies in the trade-off between the quality and the emulator size, measured by |V(H)| , the number of vertices in the emulator. Ideally, we would like to preserve all distances accurately with small-sized emulators. If there were no constraints on the structure of the emulator, then for any graph G (not necessarily planar) with k terminals, we could simply set H as the clique on the terminals and give each edge (t,t^{\prime}) length \textnormal{{dist}}_{G}(t,t^{\prime}) , trivially achieving optimal quality q=1 and optimal size |V(H)|=k . Therefore, for distance-preserving vertex sparsification to be interesting and useful, the emulator needs to inherit some structural properties from the input graph G . A natural requirement is that H be a minor of G . Such emulators are called distance-preserving minors and have been studied extensively. In the setting where q=1 , it was shown by Krauthgamer, Nguyen, and Zondiner KNZ 14 via a simple analysis that every graph G admits a quality- 1 distance-preserving minor with size O(k^{4}) , and they also proved a lower bound of \Omega(k^{2}) , leaving a gap to be closed. Another interesting setting is when |V(H)|=k , and is called the Steiner Point Removal problem (first studied by Gupta Gup 01 ), requiring that the emulator only contain terminals. For general graphs, the best achievable quality is shown to be O(\log|T|) KKN 15 ; Che 18 ; Fil 19 and \tilde{\Omega}(\sqrt{\log|T|}) CXKR 06 ; CT 24 . For minor-free graphs, after an exciting line of work BG 08 ; Fil 24 ; HL 22 ; CCL+ 23 ; CCL+ 24 , Chang, Conroy, Le, Milenkovic, Solomon and Than recently showed that quality O(1) can be achieved. Another regime that recently received much attention is planar emulators for planar graphs. The input is a planar graph G , and goal is to construct an emulator H that is also a planar graph but not necessarily a minor of G . A recent work by Chang, Krauthgamer, and Tan CKT 22 showed that quality (1+\varepsilon) can be achieved by emulators of near-linear size O(k\cdot\mathsf{poly}(\log k/\varepsilon)) . For exact (quality- 1 ) planar emulators, the best upper and lower bounds remain O(k^{4}) and \Omega(k^{2}) KNZ 14 . Recently, Chang and Ophelders CO 20 and Goranci, Henzinger, and Peng GHP 20 studied the case where all terminals lie on a single face in the planar embedding of G , and they showed that such graphs have exact planar emulators of size O(k^{2}) , which is also shown to be tight. Therefore, the natural next question is: \emph{DoeseveryplanargraphwithkterminalshaveanexactplanaremulatorofsizeO(k^{2})?} 1.1 Our Result In this paper, we make progress towards this question. Our result is summarized in the following theorem. Theorem 1 . Let G be an edge-weighted planar graph. Let T\subseteq V(G) be a set of k vertices, such that there exist f faces in the planar embedding of G that contain all vertices of T . Then there exists another edge-weighted planar graph H with T\subseteq V(H) and |V(H)|=O(f^{2}k^{2}) , such that for all t,t^{\prime}\in T , \textnormal{{dist}}_{H}(t,t^{\prime})=\textnormal{{dist}}_{G}(t,t^{\prime}) . When f takes its minimum value 1 , our result recovers the O(k^{2}) bound given by CO 20 ; GHP 20 . When f takes its maximum value k , our result recovers the O(k^{4}) bound given by KNZ 14 . Therefore, our result can be viewed as interpolating and generalizing these previous results. Unlike the previous work CO 20 which showed a universal construction and gave clean formula for directly computing edge weights from terminal distances, or the previous work GHP 20 ; KNZ 14 which constructed the emulators by performing a series of operations on the input graph, we first construct a skeleton graph that captures the shortest path structures in the input graph, and then use a linear program to find the edge weights that preserve the shortest-path distances between terminals. For the first part, our construction of the skeleton graph relies on a new understanding recently adopted in CT 25 : instead of viewing a graph as consisting of vertices and edges, we view it as being formed by paths and their intersections. For the second part, the crux is establishing the feasibility of the edge-weight linear program. We take the dual of this LP, reducing the feasibility to proving the flow-equivalence properties of certain path-morphing operations, which is then done by Wye-Delta transformations 1 1 1 The Wye-Delta transformation is a celebrated technique for analyzing electrical networks. This technique has also been used in GHP 20 for simplifying half-grid graphs with terminals on the diagonal. We employ this technique in a different way, to show non-existence of certain flows. . We believe that our approaches in both parts are of independent interest and will prove useful for more distance-based graph problems. Related Work. Chang, Gawrychowski, Mozes, and Weimann CGMW 18 also studied emulators for unweighted planar graphs, and proved that every n -vertex undirected unweighted planar graph admits an exact emulator (not necessarily planar) of size \tilde{O}(\min\{k^{2},\sqrt{kn}\}) , which is near-optimal. Organization. We provide a technical overview Section 2 , featuring our skeleton graph construction, using the 2 -face case

Read the complete text