Compact Distributed Certification of Planar Graphs

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

Algorithmica. 2021.


ArXiv version
Video at PODC (by Pedro) Video at IRIF (by Pierre)
Long version slides Teaser version slides (HALG) Teaser on the blog


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.