论文标题
嵌入平面图上的大量平行计算
Massively Parallel Computation on Embedded Planar Graphs
论文作者
论文摘要
除非1-VS-2循环猜想是错误的，否则许多经典的图形问题无法在每台机器上强烈的倍率空间和$ o（\ log n）$ rounds中解决大规模并行计算设置（MPC）。即使在平面图上也是如此。此类问题包括，例如计数连接的组件，两部分，最小跨越树问题，（近似）最短路径和（近似）直径/半径。 在本文中，我们展示了一种解决此限制的方法。具体来说，我们表明，如果我们具有输入图的``nice''（例如直线）嵌入，则可以用$ O（n^{2/3+ε}）$ o（1）$ rounds用$ o（n^{2/3+ε}）$ space解决所有提到的问题。结合现有的计算Delaunay三角剖分的算法，我们的结果暗示了使用$ O（N^{2/3 +ε}）$ O（n^{2/3 +ε}）的MPC算法，用于$ O（n^{2/3 +ε}）$，每台机器$ O（O（1）$ o（1）$。这是对标准borůvka的算法与Goodrich的Dauleanay三角算法的直接使用[Soda 1997]的首次改进，从而导致$θ（\ log n）$ rounds。这也部分负面回答了Andoni，Nikolov，Onak和Yaroslavtsev [Stoc 2014]的问题，要求确切的EMST下限。 我们将算法扩展到与不``太弯曲''的曲线组成的嵌入（按完全绝对曲率进行正式化的曲线）。我们通过新的引理进行此操作，我们认为这是独立的兴趣，并且可以用来通过全部绝对曲率来参数来参数其他几何问题。我们还可以通过计算大量的平面图。在平面图上计算了几个开放的问题。在计划上计算了计划。在平面图上计算上，可以按计划上的计算上的计算上的计算上的计算。
Many of the classic graph problems cannot be solved in the Massively Parallel Computation setting (MPC) with strongly sublinear space per machine and $o(\log n)$ 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(n^{2/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(n^{2/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 $Θ(\log n)$ 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.
