TY - GEN

T1 - Massively Parallel Computation on Embedded Planar Graphs

AU - Holm, Jacob

AU - Tětek, Jakub

PY - 2023

Y1 - 2023

N2 - Many of the classic graph problems cannot be solved in the Massively Parallel Computation setting (MPC) with strongly sublinear space per machine and o(logn) rounds, unless the 1-vs-2 cycles conjecture is false. This is true even on planar graphs. Such problems include, for example, counting connected components, bipartition, minimum spanning tree problem, (approximate) shortest paths, and (approximate) diameter/radius.In this paper, we show a way to get around this limitation. Specifically, we show that if we have a ``nice'' (for example, straight-line) embedding of the input graph, all the mentioned problems can be solved with O(n2/3+ϵ) space per machine in O(1) rounds. In conjunction with existing algorithms for computing the Delaunay triangulation, our results imply an MPC algorithm for exact Euclidean minimum spanning thee (EMST) that uses O(n2/3+ϵ) space per machine and finishes in O(1) rounds. This is the first improvement over a straightforward use of the standard Borůvka's algorithm with the Dauleanay triangulation algorithm of Goodrich [SODA 1997] which results in Θ(logn) rounds. This also partially negatively answers a question of Andoni, Nikolov, Onak, and Yaroslavtsev [STOC 2014], asking for lower bounds for exact EMST.We extend our algorithms to work with embeddings consisting of curves that are not ``too squiggly" (as formalized by the total absolute curvature). We do this via a new lemma which we believe is of independent interest and could be used to parameterize other geometric problems by the total absolute curvature. We also state several open problems regarding massively parallel computation on planar graphs.

AB - Many of the classic graph problems cannot be solved in the Massively Parallel Computation setting (MPC) with strongly sublinear space per machine and o(logn) rounds, unless the 1-vs-2 cycles conjecture is false. This is true even on planar graphs. Such problems include, for example, counting connected components, bipartition, minimum spanning tree problem, (approximate) shortest paths, and (approximate) diameter/radius.In this paper, we show a way to get around this limitation. Specifically, we show that if we have a ``nice'' (for example, straight-line) embedding of the input graph, all the mentioned problems can be solved with O(n2/3+ϵ) space per machine in O(1) rounds. In conjunction with existing algorithms for computing the Delaunay triangulation, our results imply an MPC algorithm for exact Euclidean minimum spanning thee (EMST) that uses O(n2/3+ϵ) space per machine and finishes in O(1) rounds. This is the first improvement over a straightforward use of the standard Borůvka's algorithm with the Dauleanay triangulation algorithm of Goodrich [SODA 1997] which results in Θ(logn) rounds. This also partially negatively answers a question of Andoni, Nikolov, Onak, and Yaroslavtsev [STOC 2014], asking for lower bounds for exact EMST.We extend our algorithms to work with embeddings consisting of curves that are not ``too squiggly" (as formalized by the total absolute curvature). We do this via a new lemma which we believe is of independent interest and could be used to parameterize other geometric problems by the total absolute curvature. We also state several open problems regarding massively parallel computation on planar graphs.

U2 - 10.1137/1.9781611977554.ch167

DO - 10.1137/1.9781611977554.ch167

M3 - Article in proceedings

SP - 4373

EP - 4408

BT - Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

A2 - Bansal, Nikhil

A2 - Nagarajan, Viswanath

PB - Society for Industrial and Applied Mathematics

Y2 - 22 January 2023 through 25 January 2023

ER -