Three Unintuitive Facts about Distances on Planar Graphs (以英文演講)
- 講者Hsien-Chih Chang 教授 (Department of Computer Science, Dartmouth College, USA)
邀請人：蔡孟宗 - 時間2025-07-09 (Wed.) 10:00 ~ 12:00
- 地點資訊所新館106演講廳
摘要
Conventional wisdom told us that planar graphs are essentially edge-weighted grids, with more or less equal side-lengths. An n-node n^{1/2}-by-n^{1/2} square grid has treewidth Θ(n^{1/2}); and if we want to preserve shortest-path distances between every pair of boundary nodes, intuitively we have to keep all the n^{1/2} column and row paths, which together create n "crossings" that cannot be removed. This seems to suggest that planar graphs are incompressible and not tree-like. Or does it?
In this talk we will discuss three unintuitive, and perhaps surprising, facts about planar metrics in the (1+ε)-approximation regime. First we demonstrate how to construct emulator for planar graphs that preserves distances between k terminals, that has size O_[@BackSlash]e(k polylog k). (This implies, for the grid example above, the resulting emulator has size [@BackSlash]tilde{O}(n^{1/2}).)
Second, planar metrics can be sketched/covered using constantly(!) many trees, in the sense that we can construct O(1) many trees independent to the size of the input graph that never shrinks distances, so that given any pair of nodes x and y, there is one tree T that contains both x and y whose distance on T is stretched by at most a 1+ε factor. Along the way we will introduce a novel structure on planar metrics --- the gridtrees --- that enables such tree covers, as well as its applications in the resolution to the Steiner point removal problem, and in constructing embeddings of planar graphs into polylog-treewidth graphs with (1+ε)-distortion. (Which means, if we are willing to distort the distance by a small amount, planar metrics are very much tree-like, against our intuition.)
Finally, we will discuss the issue of _spanning_. Both results above rely on the fact that the emulator and the tree cover use "Steiner nodes", which are nodes not presented in the original input graph. Maybe this is cheating, and the distance compression is only possible because of these nodes that appear out of nowhere? Our goal is to convince you otherwise: We can in fact construct emulators for planar graphs that are _minors_, which only uses paths and edges from the input planar graph; and in the case of tree covers, we are one or two new structures away from enforcing the trees to be spanning, that is, the edges in the trees have come from the input graph as well.
If time permits, we will conclude the talk with some future directions and open questions.
Acknowledgement:
The results we discuss in this talk are a combination of my research in the past few years with many collaborators. The emulator result is from STOC 2022 with Zihan Tan; the tree cover result comes from the papers from FOCS 2023 and SODA 2024, which is a joint work with the tree cover group consisting of Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than. The distance approximating minor result is from a work submitted to FOCS 2025 with Jonathan, and the spanning tree cover result is again by the tree cover group, accepted to STOC 2025.
In this talk we will discuss three unintuitive, and perhaps surprising, facts about planar metrics in the (1+ε)-approximation regime. First we demonstrate how to construct emulator for planar graphs that preserves distances between k terminals, that has size O_[@BackSlash]e(k polylog k). (This implies, for the grid example above, the resulting emulator has size [@BackSlash]tilde{O}(n^{1/2}).)
Second, planar metrics can be sketched/covered using constantly(!) many trees, in the sense that we can construct O(1) many trees independent to the size of the input graph that never shrinks distances, so that given any pair of nodes x and y, there is one tree T that contains both x and y whose distance on T is stretched by at most a 1+ε factor. Along the way we will introduce a novel structure on planar metrics --- the gridtrees --- that enables such tree covers, as well as its applications in the resolution to the Steiner point removal problem, and in constructing embeddings of planar graphs into polylog-treewidth graphs with (1+ε)-distortion. (Which means, if we are willing to distort the distance by a small amount, planar metrics are very much tree-like, against our intuition.)
Finally, we will discuss the issue of _spanning_. Both results above rely on the fact that the emulator and the tree cover use "Steiner nodes", which are nodes not presented in the original input graph. Maybe this is cheating, and the distance compression is only possible because of these nodes that appear out of nowhere? Our goal is to convince you otherwise: We can in fact construct emulators for planar graphs that are _minors_, which only uses paths and edges from the input planar graph; and in the case of tree covers, we are one or two new structures away from enforcing the trees to be spanning, that is, the edges in the trees have come from the input graph as well.
If time permits, we will conclude the talk with some future directions and open questions.
Acknowledgement:
The results we discuss in this talk are a combination of my research in the past few years with many collaborators. The emulator result is from STOC 2022 with Zihan Tan; the tree cover result comes from the papers from FOCS 2023 and SODA 2024, which is a joint work with the tree cover group consisting of Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than. The distance approximating minor result is from a work submitted to FOCS 2025 with Jonathan, and the spanning tree cover result is again by the tree cover group, accepted to STOC 2025.