Skip to Main content Skip to Navigation
Conference papers

Compact Distributed Certification of Planar Graphs

Abstract : 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(log n) 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(log n) bits. We also show that there are no proof-labeling schemes-in fact, even no locally checkable proofs-for planarity using certificates on o(log n) bits.
Complete list of metadata

Cited literature [45 references]  Display  Hide  Download
Contributor : Nelly Wirth Connect in order to contact the contributor
Submitted on : Friday, November 6, 2020 - 11:23:28 AM
Last modification on : Wednesday, November 3, 2021 - 7:33:28 AM
Long-term archiving on: : Sunday, February 7, 2021 - 6:40:40 PM


Compact Distributed Certificat...
Files produced by the author(s)



Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, et al.. Compact Distributed Certification of Planar Graphs. 39th ACM Symposium on Principles of Distributed Computing, Aug 2020, Virtual Event Italy, Italy. pp.319-328, ⟨10.1145/3382734.3404505⟩. ⟨halshs-02991868⟩



Record views


Files downloads