IDEAS home Printed from https://ideas.repec.org/p/hal/journl/halshs-02991868.html
   My bibliography  Save this paper

Compact Distributed Certification of Planar Graphs

Author

Listed:
  • Laurent Feuilloley

    (UCHILE - Universidad de Chile = University of Chile [Santiago])

  • Pierre Fraigniaud

    (IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale - CNRS - Centre National de la Recherche Scientifique - UPCité - Université Paris Cité)

  • Pedro Montealegre

    (Universidad Adolfo Ibáñez [Santiago])

  • Ivan Rapaport

    (CMM - Centre de modélisation mathématique / Centro de Modelamiento Matemático [Santiago] - UCHILE - Universidad de Chile = University of Chile [Santiago] - CNRS - Centre National de la Recherche Scientifique)

  • Éric Rémila

    (GATE Lyon Saint-Étienne - Groupe d'Analyse et de Théorie Economique Lyon - Saint-Etienne - ENS de Lyon - École normale supérieure de Lyon - UL2 - Université Lumière - Lyon 2 - UCBL - Université Claude Bernard Lyon 1 - Université de Lyon - UJM - Université Jean Monnet - Saint-Étienne - CNRS - Centre National de la Recherche Scientifique)

  • Ioan Todinca

    (LIFO - Laboratoire d'Informatique Fondamentale d'Orléans - UO - Université d'Orléans - INSA CVL - Institut National des Sciences Appliquées - Centre Val de Loire - INSA - Institut National des Sciences Appliquées)

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.

Suggested Citation

  • Laurent Feuilloley & Pierre Fraigniaud & Pedro Montealegre & Ivan Rapaport & Éric Rémila & Ioan Todinca, 2020. "Compact Distributed Certification of Planar Graphs," Post-Print halshs-02991868, HAL.
    • Handle: RePEc:hal:journl:halshs-02991868
    DOI: 10.1145/3382734.3404505
    Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-02991868
    as

    Download full text from publisher

    File URL: https://shs.hal.science/halshs-02991868/document
    Download Restriction: no
    File URL: https://libkey.io/10.1145/3382734.3404505?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:journl:halshs-02991868. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.