Covering Planar Metrics (and Beyond): O(1) Trees Suffice
Published in FOCS, 2023
We propose an algorithm constructing a $\epsilon$ -distortion tree cover for planar metrics of size $O_\epsilon(1)$. We also improve the embedding algorithm for planar graph into a bounded treedwidth graph with additive distortion
Recommended citation: HC Chang, J Conroy, H Le, L Milenkovic, S Solomon, C Than. (2023). "Covering Planar Metrics (and Beyond): O(1) Trees Suffice ." The 64th IEEE Symposium on Foundations of Computer Science (FOCS) 2023.