Naor, Parter, and Yogev (SODA 2020) have recently demonstrated
the existence of a
distributed interactive proof for
planarity (i.e., for certifying that a network is planar), using
a sophisticated generic technique for constructing distributed
IP protocols based on sequential IP protocols. The interactive
proof for planarity is based on a distributed certification of
the correct execution of any given sequential linear-time
algorithm for planarity testing. It involves three interactions
between the prover and the randomized distributed verifier (i.e.,
it is a dMAM protocol), and uses small certificates, on O(logn)
bits in n-node networks. We show that a single interaction from
the prover suffices, and randomization is unecessary, by
providing an explicit description of a
proof-labeling scheme
for planarity, still using certificates on just O(logn) bits.
We also show that there are no proof-labeling schemes -- in
fact, even no
locally checkable proofs -- for planarity
using certificates on o(logn) bits.
