Property Testing of Planarity in the CONGEST model
Property Testing of Planarity in the CONGEST model
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 …