Compact Distributed Certification of Planar Graphs

Laurent Feuilloley, Pierre Fraigniaud, Ivan Rapaport, Éric Rémila, Pedro Montealegre, Ioan Todinca.

Algorithmica. 2021.
doi:10.1007/s00453-021-00823-w.

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.

The paper originates from a research visit of Pierre and Ioan in Chile in February 2020. The paper appeared in a conference version in PODC 2020.

Pedro presented the paper at PODC 2020. Ioan presented the paper at HALG 2020 (with the teaser version slides above). I presented the paper at the GRAA seminar (Graphe en Rhone-Alpes Auvergne). Pierre presented the paper at the IRIF graph seminar in October 2020.

I presented the paper in 2021, along with newer results, at Bordeaux's Distributed Algorithms Seminar and at Sophia-Antipolis/Nice's COATI Seminar.

With the same team, we proved that we can actually certify not only planar graphs, but bounded genus graphs with logarithmic certificates. See arxiv:2007.08084.

Recentely the same results were obtained by Esperet and Leveque using completely different techniques. See arxiv:2102.04133.