Jakub Tetek, University of Copenhagen

Abstract

While algorithms for planar graphs have received a lot of attention, few papers have focused on the additional power that one gets from assuming an embedding of the graph is available. While in the classic sequential setting, this assumption gives no additional power, we show that this is far from being the case in other settings. Specifically, we focus on sublinear-time
computation and massively parallel computation (MPC).

We show sublinear-time algorithms for approximating Lipschitz additive graph parameters. This includes, for example, the maximum matching, maximum independent set, or the minimum dominating set. We give a technique for designing MPC algorithms for embedded planar graphs that leads to O(1) round algorithms with O(n2/3+ε) space per machine for: counting connected components, bipartition, minimum spanning tree problem, O(1)-approximate shortest paths, O(1)-approximate diameter/radius. Our results imply an improved MPC algorithm for Euclidean MST.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar