Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., Remila, E., & Todinca, I. (2021). Compact Distributed Certification of Planar Graphs. Algorithmica, Early Access.
Abstract: Naor M., Parter M., Yogev E.: (The power of distributed verifiers in interactive proofs. In: 31st ACMSIAM symposium on discrete algorithms (SODA), pp 1096115, 2020. https://doi.org/10.1137/1.9781611975994.67) 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 lineartime 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(log n) bits in nnode networks. We show that a single interaction with the prover suffices, and randomization is unecessary, by providing an explicit description of a prooflabeling scheme for planarity, still using certificates on just O(log n) bits. We also show that there are no prooflabeling schemesin fact, even no locally checkable proofsfor planarity using certificates on o(log n) bits.
