2018/05/27 by Levi, Reut, Medina, Moti, Ron, Dana · 1 citation
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1805.10657
We give a distributed algorithm in the \sf CONGEST model for property testing of planarity with one-sided error in general (unbounded-degree) graphs. Following Censor-Hillel et al. (DISC 2016), who recently initiated the study of property testing in the distributed setting, our algorithm gives the following guarantee: For a graph G = (V,E) and a distance parameter ε, if G is planar, then every node outputs \sf accept\/, and if G is ε-far from being planar (i.e., more than ε⋅ |E| edges need to be removed in order to make G planar), then with probability 1-1/\rm poly(n) at least one node outputs \sf reject. The algorithm runs in O(log|V|⋅\rm poly(1/ε)) rounds, and we show that this result is tight in terms of the dependence on |V|. Our algorithm combines several techniques of graph partitioning and local verification of planar embeddings. Furthermore, we show how a main subroutine in our algorithm can be applied to derive additional results for property testing of cycle-freeness and bipartiteness, as well as the construction of spanners, in minor-free (unweighted) graphs.