We provide new communication-efficient distributed interactive proofs for planarity. The notion of a \emph{ distributed interactive proof (DIP)} was introduced by Kol, Oshman, and Saxena (PODC 2018). In a DIP, the \emph{ prover} is a single centralized entity whose goal is to prove a certain claim regarding an input graph $G$. To do so, the prover communicates with a distributed \emph{ verifier} that operates concurrently on all $n$ nodes of $G$. A DIP is measured by the amount of prover-verifier communication it requires. Namely, the goal is to design a DIP with a small number of interaction rounds and a small \emph{ proof size}, i.e., a small amount of communication per round. Our main result is an $O(\log ^{ *}n)$-round DIP protocol for embedded planarity and planarity with a proof size of $O(1)$ and $O(\lceil\log \Delta/\log ^{ *}n\rceil)$, respectively. In fact, this result can be generalized as follows. For any $1\leq r\leq \log^{ *}n$, there exists an $O(r)$-round protocol for embedded planarity and planarity with a proof size of $O(\log ^{ (r)}n)$ and $O(\log ^{ (r)}n+\log \Delta /r)$, respectively.
Categories: cs.DC cs.DS