Almost-linear ε -emulators for planar graphs

DOI10.1145/3519935.3519998MaRDI QIDQ6083585zbMATH OpenFDO

Authors Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.10681

zbMATH Keywords

emulatorOkamura-Seymour instanceplanar metricslicingspread reduction

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph $G$ (with edge weights) and a subset of $k$ terminal vertices, the goal is to construct an $varepsilon$-emulator, which is a small planar graph $G^{\prime }$ that contains the terminals and preserves the distances between the terminals up to factor $1+varepsilon$. We construct the first $varepsilon$-emulators for planar graphs of near-linear size $ildeO(k/varepsilo{n}^{O(1)})$. In terms of $k$, this is a dramatic improvement over the previous quadratic upper bound of Cheung, Goranci and Henzinger, and breaks below known quadratic lower bounds for exact emulators (the case when $varepsilon=0$). Moreover, our emulators can be computed in (near-)linear time, which lead to fast $(1+varepsilon)$-approximation algorithms for basic optimization problems on planar graphs, including multiple-source shortest paths, minimum $(s,t)$-cut, graph diameter, and dynamic distace oracle.

Recommendations

• Near-optimal distance emulator for planar graphs
• On almost-planar graphs
• Towards finite characterization of planar-emulable non-projective graphs
• scientific article; zbMATH DE number 3968606
• Planar emulators conjecture is nearly true for cubic graphs
• scientific article; zbMATH DE number 6302995
• scientific article; zbMATH DE number 3968607
• How not to characterize planar-emulable graphs
• How not to characterize planar-emulable graphs
• On the linearity of testing planarity of graphs

Cited in

(3)

• scientific article; zbMATH DE number 6302995 (Why is no real title available?)
• Shortest path separators in unit disk graphs
• Title not available (Why is no real title available?)

This page was built for publication: Almost-linear ε -emulators for planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083585)