Planarity is (almost) locally checkable in constant-time
share
Locally checkable proofs for graph properties were introduced by Göös and Suomela <cit.>. Roughly speaking, a graph property is locally checkable in constant-time, if the vertices of a graph having the property can be convinced, in a short period of time not depending on the size of the graph, that they are indeed vertices of a graph having the given property. For a given >0, we call a property -locally checkable in constant-time if the vertices of a graph having the given property can be convinced at least that they are in a graph -close to the given property. We say that a property is almost locally checkable in constant-time, if for all >0, is -locally checkable in constant-time. It is not hard to see that in the universe of bounded degree graphs planarity is not locally checkable in constant-time. However, the main result of this paper is that planarity of bounded degree graphs is almost locally checkable in constant-time. The proof is based on the surprising fact that although graphs cannot be convinced by their planarity or hyperfiniteness, planar graphs can be convinced by their own hyperfiniteness. The reason behind this fact is that the class of planar graphs are not only hyperfinite but possesses Property A of Yu.
READ FULL TEXT