Distributed Interactive Proofs for Planarity with Log-Star Communication

We provide new communication-efficient distributed interactive proofs for planarity. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In a DIP, the 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 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 proof size, i.e., a small amount of communication per round.