{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:15Z","timestamp":1759638375962,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T00:00:00Z","timestamp":1596153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,31]]},"DOI":"10.1145\/3382734.3404505","type":"proceedings-article","created":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T22:33:55Z","timestamp":1596234835000},"page":"319-328","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Compact Distributed Certification of Planar Graphs"],"prefix":"10.1145","author":[{"given":"Laurent","family":"Feuilloley","sequence":"first","affiliation":[{"name":"Universidad de Chile, Chile"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Paris, France"}]},{"given":"Pedro","family":"Montealegre","sequence":"additional","affiliation":[{"name":"Universidad Adolfo Iba\u00f1ez, Santiago, Chile"}]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[{"name":"Universidad de Chile, Chile"}]},{"given":"\u00c9ric","family":"R\u00e9mila","sequence":"additional","affiliation":[{"name":"GATE Lyon St-Etienne, France"}]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[{"name":"Universit\u00e9 d'Orl\u00e9ans, France"}]}],"member":"320","published-online":{"date-parts":[[2020,7,31]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00286-1"},{"key":"e_1_3_2_1_2_1","volume-title":"Distributed Domination on Graph Classes of Bounded Expansion. In 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 143--151","author":"Amiri Saeed Akhoondian","year":"2018","unstructured":"Saeed Akhoondian Amiri , Patrice Ossona de Mendez , Roman Rabinovich , and Sebastian Siebertz . 2018 . Distributed Domination on Graph Classes of Bounded Expansion. In 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 143--151 . Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, and Sebastian Siebertz. 2018. Distributed Domination on Graph Classes of Bounded Expansion. In 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 143--151."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326170"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90083-3"},{"key":"e_1_3_2_1_5_1","volume-title":"32nd Symposium on Foundations of Computer Science (FOCS). 268--277","author":"Awerbuch Baruch","year":"1991","unstructured":"Baruch Awerbuch , Boaz Patt-Shamir , and George Varghese . 1991 . Self-Stabilization By Local Checking and Correction (Extended Abstract) . In 32nd Symposium on Foundations of Computer Science (FOCS). 268--277 . Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. 1991. Self-Stabilization By Local Checking and Correction (Extended Abstract). In 32nd Symposium on Foundations of Computer Science (FOCS). 268--277."},{"key":"e_1_3_2_1_6_1","volume-title":"34th Symposium on Theoretical Aspects of Computer Science (STACS). 8:1--8:13","author":"Balliu Alkida","year":"2017","unstructured":"Alkida Balliu , Gianlorenzo D'Angelo , Pierre Fraigniaud , and Dennis Olivetti . 2017 . What Can Be Verified Locally? . In 34th Symposium on Theoretical Aspects of Computer Science (STACS). 8:1--8:13 . Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, and Dennis Olivetti. 2017. What Can Be Verified Locally?. In 34th Symposium on Theoretical Aspects of Computer Science (STACS). 8:1--8:13."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3218821"},{"key":"e_1_3_2_1_8_1","volume-title":"Trade-Offs in Distributed Interactive Proofs. In 33rd International Symposium on Distributed Computing (DISC) (LIPIcs 146)","author":"Crescenzi Pierluigi","year":"2019","unstructured":"Pierluigi Crescenzi , Pierre Fraigniaud , and Ami Paz . 2019 . Trade-Offs in Distributed Interactive Proofs. In 33rd International Symposium on Distributed Computing (DISC) (LIPIcs 146) . Dagstuhl, 13:1--13:17. Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz. 2019. Trade-Offs in Distributed Interactive Proofs. In 33rd International Symposium on Distributed Computing (DISC) (LIPIcs 146). Dagstuhl, 13:1--13:17."},{"key":"e_1_3_2_1_9_1","volume-title":"Distributed Approximation Algorithms for Planar Graphs. In 6th Italian Conference on Algorithms and Complexity (CIAC). 296--307","author":"Czygrinow Andrzej","year":"2006","unstructured":"Andrzej Czygrinow , Micha\u0142 Ha\u0144\u0107kowiak , and Edyta Szymanska . 2006 . Distributed Approximation Algorithms for Planar Graphs. In 6th Italian Conference on Algorithms and Complexity (CIAC). 296--307 . Andrzej Czygrinow, Micha\u0142 Ha\u0144\u0107kowiak, and Edyta Szymanska. 2006. Distributed Approximation Algorithms for Planar Graphs. In 6th Italian Conference on Algorithms and Complexity (CIAC). 296--307."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-14472-6_4"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.12.001"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378541"},{"key":"e_1_3_2_1_13_1","volume-title":"Fast Distributed Approximations in Planar Graphs. In 22nd Int. Symp. on Distributed Computing (DISC). 78--92","author":"Czygrinow Andrzej","year":"2008","unstructured":"Andrzej Czygrinow , Micha\u0142 Ha\u0144\u0107kowiak , and Wojciech Wawrzyniak . 2008 . Fast Distributed Approximations in Planar Graphs. In 22nd Int. Symp. on Distributed Computing (DISC). 78--92 . Andrzej Czygrinow, Micha\u0142 Ha\u0144\u0107kowiak, and Wojciech Wawrzyniak. 2008. Fast Distributed Approximations in Planar Graphs. In 22nd Int. Symp. on Distributed Computing (DISC). 78--92."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579375"},{"volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"Diestel Reinhard","key":"e_1_3_2_1_15_1","unstructured":"Reinhard Diestel . 2000. Graph Theory. Graduate Texts in Mathematics , Vol. 173 . Springer-Verlag . Reinhard Diestel. 2000. Graph Theory. Graduate Texts in Mathematics, Vol. 173. Springer-Verlag."},{"key":"e_1_3_2_1_16_1","volume-title":"Introduction to local certification. CoRR abs\/1910.12747","author":"Feuilloley Laurent","year":"2019","unstructured":"Laurent Feuilloley . 2019. Introduction to local certification. CoRR abs\/1910.12747 ( 2019 ). arXiv:1910.12747 Laurent Feuilloley. 2019. Introduction to local certification. CoRR abs\/1910.12747 (2019). arXiv:1910.12747"},{"key":"e_1_3_2_1_17_1","volume-title":"Bibliography of distributed approximation on structurally sparse graph classes. CoRR abs\/2001.08510","author":"Feuilloley Laurent","year":"2020","unstructured":"Laurent Feuilloley . 2020. Bibliography of distributed approximation on structurally sparse graph classes. CoRR abs\/2001.08510 ( 2020 ). arXiv:2001.08510 Laurent Feuilloley. 2020. Bibliography of distributed approximation on structurally sparse graph classes. CoRR abs\/2001.08510 (2020). arXiv:2001.08510"},{"key":"e_1_3_2_1_18_1","volume-title":"Survey of Distributed Decision. Bulletin of the EATCS 119","author":"Feuilloley Laurent","year":"2016","unstructured":"Laurent Feuilloley and Pierre Fraigniaud . 2016. Survey of Distributed Decision. Bulletin of the EATCS 119 ( 2016 ). Laurent Feuilloley and Pierre Fraigniaud. 2016. Survey of Distributed Decision. Bulletin of the EATCS 119 (2016)."},{"key":"e_1_3_2_1_19_1","first-page":"1","article-title":"A Hierarchy of Local Decision. In 43rd International Colloquium on Automata","volume":"118","author":"Feuilloley Laurent","year":"2016","unstructured":"Laurent Feuilloley , Pierre Fraigniaud , and Juho Hirvonen . 2016 . A Hierarchy of Local Decision. In 43rd International Colloquium on Automata , Languages and Programming (ICALP). 118 : 1 -- 118 :15. Laurent Feuilloley, Pierre Fraigniaud, and Juho Hirvonen. 2016. A Hierarchy of Local Decision. In 43rd International Colloquium on Automata, Languages and Programming (ICALP). 118:1--118:15.","journal-title":"Languages and Programming (ICALP)."},{"key":"e_1_3_2_1_20_1","first-page":"1","article-title":"Redundancy in Distributed Proofs. In 32nd International Symposium on Distributed Computing (DISC) (LIPIcs)","volume":"24","author":"Feuilloley Laurent","year":"2018","unstructured":"Laurent Feuilloley , Pierre Fraigniaud , Juho Hirvonen , Ami Paz , and Mor Perry . 2018 . Redundancy in Distributed Proofs. In 32nd International Symposium on Distributed Computing (DISC) (LIPIcs) . Dagstuhl , 24 : 1 -- 24 :18. Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry. 2018. Redundancy in Distributed Proofs. In 32nd International Symposium on Distributed Computing (DISC) (LIPIcs). Dagstuhl, 24:1--24:18.","journal-title":"Dagstuhl"},{"key":"e_1_3_2_1_21_1","volume-title":"Local Verification of Global Proofs. In 32nd Int. Symp. on Distributed Computing (DISC) (LIPIcs 121)","author":"Feuilloley Laurent","year":"2018","unstructured":"Laurent Feuilloley and Juho Hirvonen . 2018 . Local Verification of Global Proofs. In 32nd Int. Symp. on Distributed Computing (DISC) (LIPIcs 121) . Dagstuhl, 25:1--25:17. Laurent Feuilloley and Juho Hirvonen. 2018. Local Verification of Global Proofs. In 32nd Int. Symp. on Distributed Computing (DISC) (LIPIcs 121). Dagstuhl, 25:1--25:17."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499228"},{"volume-title":"26th Int. Colloquium Structural Information and Communication Complexity (SIROCCO) (LNCS 11639)","author":"Fraigniaud Pierre","key":"e_1_3_2_1_23_1","unstructured":"Pierre Fraigniaud , Pedro Montealegre , Rotem Oshman , Ivan Rapaport , and Ioan Todinca . 2019. On Distributed Merlin-Arthur Decision Protocols . In 26th Int. Colloquium Structural Information and Communication Complexity (SIROCCO) (LNCS 11639) . Springer , 230--245. Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. 2019. On Distributed Merlin-Arthur Decision Protocols. In 26th Int. Colloquium Structural Information and Communication Complexity (SIROCCO) (LNCS 11639). Springer, 230--245."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0340-8"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001814"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933109"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"e_1_3_2_1_28_1","volume-title":"Near-Optimal Distributed DFS in Planar Graphs. In 31st Int. Symp. on Distributed Computing (DISC) (LIPIcs). Dagstuhl, 21:1--21:16","author":"Ghaffari Mohsen","year":"2017","unstructured":"Mohsen Ghaffari and Merav Parter . 2017 . Near-Optimal Distributed DFS in Planar Graphs. In 31st Int. Symp. on Distributed Computing (DISC) (LIPIcs). Dagstuhl, 21:1--21:16 . Mohsen Ghaffari and Merav Parter. 2017. Near-Optimal Distributed DFS in Planar Graphs. In 31st Int. Symp. on Distributed Computing (DISC) (LIPIcs). Dagstuhl, 21:1--21:16."},{"key":"e_1_3_2_1_29_1","first-page":"1","article-title":"Locally Checkable Proofs in Distributed Computing","volume":"12","author":"G\u00f6\u00f6s Mika","year":"2016","unstructured":"Mika G\u00f6\u00f6s and Jukka Suomela . 2016 . Locally Checkable Proofs in Distributed Computing . Theory of Computing 12 , 1 (2016), 1 -- 33 . Mika G\u00f6\u00f6s and Jukka Suomela. 2016. Locally Checkable Proofs in Distributed Computing. Theory of Computing 12, 1 (2016), 1--33.","journal-title":"Theory of Computing"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611504"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"volume-title":"Fast and Lean Self-Stabilizing Asynchronous Protocols. In 35th IEEE Symp. on Foundations of Computer Science (FOCS). 226--239","author":"Itkis Gene","key":"e_1_3_2_1_32_1","unstructured":"Gene Itkis and Leonid A. Levin . 1994 . Fast and Lean Self-Stabilizing Asynchronous Protocols. In 35th IEEE Symp. on Foundations of Computer Science (FOCS). 226--239 . Gene Itkis and Leonid A. Levin. 1994. Fast and Lean Self-Stabilizing Asynchronous Protocols. In 35th IEEE Symp. on Foundations of Computer Science (FOCS). 226--239."},{"volume-title":"Interactive Distributed Proofs. In ACM Symposium on Principles of Distributed Computing (PODC). 255--264","author":"Kol Gillat","key":"e_1_3_2_1_33_1","unstructured":"Gillat Kol , Rotem Oshman , and Raghuvansh R. Saxena . 2018 . Interactive Distributed Proofs. In ACM Symposium on Principles of Distributed Computing (PODC). 255--264 . Gillat Kol, Rotem Oshman, and Raghuvansh R. Saxena. 2018. Interactive Distributed Proofs. In ACM Symposium on Principles of Distributed Computing (PODC). 255--264."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378540"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0186-z"},{"key":"e_1_3_2_1_38_1","volume-title":"The Power of Distributed Verifiers in Interactive Proofs. In 31st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1096--115","author":"Naor Moni","year":"2020","unstructured":"Moni Naor , Merav Parter , and Eylon Yogev . 2020 . The Power of Distributed Verifiers in Interactive Proofs. In 31st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1096--115 . Moni Naor, Merav Parter, and Eylon Yogev. 2020. The Power of Distributed Verifiers in Interactive Proofs. In 31st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1096--115."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369740"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80007-2"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.11.008"}],"event":{"name":"PODC '20: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Event Italy","acronym":"PODC '20"},"container-title":["Proceedings of the 39th Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382734.3404505","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382734.3404505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:49Z","timestamp":1750197769000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382734.3404505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,31]]},"references-count":44,"alternative-id":["10.1145\/3382734.3404505","10.1145\/3382734"],"URL":"https:\/\/doi.org\/10.1145\/3382734.3404505","relation":{},"subject":[],"published":{"date-parts":[[2020,7,31]]},"assertion":[{"value":"2020-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}