We look forward to seeing you in person in 3401 Siebel Center for Computer Science.
Abstract: The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenkovic, Solomon, and Than [FOCS23, SODA24], is a new type of graph partition into low-diameter clusters. Roughly speaking, the shortcut partition guarantees that for every two vertices u and v in the graph, there exists a path between u and v that intersects only constantly many clusters; put it differently, the _hop-diameter_ of the graph formed by contracting all the clusters is bounded.
In this talk we explain how to construct shortcut partitions for planar graphs (and minor-free graphs, if time permits). Next we give several applications. First, we demonstrate the existence of _tree cover_ for arbitrary planar graphs with stretch 1+ε and O(1) many trees for any fixed ε. Specifically, a tree cover [AP92, GKR01, BFN19] of a metric space (X, δ) is a collection of trees, so that every pair of points u and v in X has a low-distortion path in at least one of the trees. Next, we showcase the applicability of tree covers by constructing distance oracles, emulators, and a simpler and better embedding of planar graphs into O(1)-treewidth graphs with small additive distortion, resolving an open problem in this line of research [FKS19].
As a highlight of our work, we employ our shortcut partition to resolve a major open problem — the Steiner point removal (SPR) problem: Given any set K of terminals in an arbitrary edge-weighted planar graph G, is it possible to construct a minor M of G whose vertex set is K, which preserves the shortest-path distances between all pairs of terminals in G up to a constant factor? Positive answers to the SPR problem were only known for very restricted classes of planar graphs: trees [Gup01], outerplanar graphs [BG08], and series-parallel graphs [HL22]. We resolve the SPR problem in the affirmative for any planar graph, and more generally for any K_r-minor-free graph for any fixed r.
Joint work with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than. https://arxiv.org/abs/2308.00555 .
