{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:42:20Z","timestamp":1782970940416,"version":"3.54.5"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2021,5,6]],"date-time":"2021-05-06T00:00:00Z","timestamp":1620259200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,6]],"date-time":"2021-05-06T00:00:00Z","timestamp":1620259200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s00453-021-00823-w","type":"journal-article","created":{"date-parts":[[2021,5,6]],"date-time":"2021-05-06T09:03:13Z","timestamp":1620291793000},"page":"2215-2244","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Compact Distributed Certification of Planar Graphs"],"prefix":"10.1007","volume":"83","author":[{"given":"Laurent","family":"Feuilloley","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2508-5907","authenticated-orcid":false,"given":"Pedro","family":"Montealegre","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00c9ric","family":"R\u00e9mila","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,5,6]]},"reference":[{"issue":"1\u20132","key":"823_CR1","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0304-3975(96)00286-1","volume":"186","author":"Y Afek","year":"1997","unstructured":"Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its application to self-stabilization. Theor. Comput. Sci. 186(1\u20132), 199\u2013229 (1997). https:\/\/doi.org\/10.1016\/S0304-3975(96)00286-1","journal-title":"Theor. Comput. Sci."},{"key":"823_CR2","doi-asserted-by":"publisher","unstructured":"Amiri, S.A., de\u00a0Mendez, P.O., Rabinovich, R., Siebertz, S.: Distributed domination on graph classes of bounded expansion. In: 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 143\u2013151 (2018). https:\/\/doi.org\/10.1145\/3210377.3210383","DOI":"10.1145\/3210377.3210383"},{"issue":"3","key":"823_CR3","doi-asserted-by":"publisher","first-page":"39:1","DOI":"10.1145\/3326170","volume":"15","author":"SA Amiri","year":"2019","unstructured":"Amiri, S.A., Schmid, S., Siebertz, S.: Distributed dominating set approximations beyond planar graphs. ACM Trans. Algorithms 15(3), 39:1\u2013139:8 (2019). https:\/\/doi.org\/10.1145\/3326170","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"823_CR4","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0020-0190(85)90083-3","volume":"20","author":"B Awerbuch","year":"1985","unstructured":"Awerbuch, B.: A new distributed depth-first-search algorithm. Inf. Process. Lett. 20(3), 147\u2013150 (1985). https:\/\/doi.org\/10.1016\/0020-0190(85)90083-3","journal-title":"Inf. Process. Lett."},{"key":"823_CR5","doi-asserted-by":"publisher","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction (extended abstract). In: 32nd Symposium on Foundations of Computer Science (FOCS), pp. 268\u2013277 (1991). https:\/\/doi.org\/10.1109\/SFCS.1991.185378","DOI":"10.1109\/SFCS.1991.185378"},{"key":"823_CR6","doi-asserted-by":"publisher","unstructured":"Balliu, A., D\u2019Angelo, G., Fraigniaud, P., Olivetti, D.: What can be verified locally? pp. 8:1\u20138:13 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2017.8","DOI":"10.4230\/LIPIcs.STACS.2017.8"},{"issue":"2","key":"823_CR7","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/3218821","volume":"15","author":"S Cabello","year":"2019","unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Trans. Algorithms 15(2), 21:1\u2013321:8 (2019). https:\/\/doi.org\/10.1145\/3218821","journal-title":"ACM Trans. Algorithms"},{"key":"823_CR8","doi-asserted-by":"publisher","unstructured":"Crescenzi, P., Fraigniaud, P., Paz, A.: Trade-offs in distributed interactive proofs. In: 33rd International Symposium on Distributed Computing (DISC), LIPIcs 146, pp. 13:1\u201313:17. Dagstuhl (2019). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2019.13","DOI":"10.4230\/LIPIcs.DISC.2019.13"},{"key":"823_CR9","doi-asserted-by":"publisher","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Szymanska, E.: Distributed approximation algorithms for planar graphs. In: 6th Italian Conference on Algorithms and Complexity (CIAC), pp. 296\u2013307 (2006). https:\/\/doi.org\/10.1007\/11758471_29","DOI":"10.1007\/11758471_29"},{"key":"823_CR10","doi-asserted-by":"publisher","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Szymanska, E., Wawrzyniak, W., Witkowski, M.: Distributed local approximation of the minimum k-tuple dominating set in planar graphs. In: 18th Int. Conference on Principles of Distributed Systems (OPODIS), pp. 49\u201359 (2014). https:\/\/doi.org\/10.1007\/978-3-319-14472-6_4","DOI":"10.1007\/978-3-319-14472-6_4"},{"key":"823_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.12.001","volume":"662","author":"A Czygrinow","year":"2017","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Szymanska, E., Wawrzyniak, W., Witkowski, M.: Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs. Theor. Comput. Sci. 662, 1\u20138 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2016.12.001","journal-title":"Theor. Comput. Sci."},{"key":"823_CR12","doi-asserted-by":"publisher","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Distributed packing in planar graphs. In: 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 55\u201361 (2008). https:\/\/doi.org\/10.1145\/1378533.1378541","DOI":"10.1145\/1378533.1378541"},{"key":"823_CR13","doi-asserted-by":"publisher","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: 22nd Int. Symp. on Distributed Computing (DISC), pp. 78\u201392 (2008). https:\/\/doi.org\/10.1007\/978-3-540-87779-0_6","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"823_CR14","volume-title":"Graph Theory, Graduate Texts in Mathematics","author":"R Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2000)"},{"key":"823_CR15","doi-asserted-by":"crossref","unstructured":"Esperet, L., L\u00e9v\u00eaque, B.: Local certification of graphs on surfaces. arXiv preprint arXiv:2102.04133 (2021)","DOI":"10.1016\/j.tcs.2022.01.023"},{"key":"823_CR16","unstructured":"Feuilloley, L.: Introduction to local certification. CoRR abs\/1910.12747 (2019). http:\/\/arxiv.org\/abs\/1910.12747"},{"key":"823_CR17","unstructured":"Feuilloley, L.: Bibliography of distributed approximation beyonf bounded degree. CoRR abs\/2001.08510 (2020). http:\/\/arxiv.org\/abs\/2001.08510"},{"key":"823_CR18","unstructured":"Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. Bulletin of the EATCS 119 (2016). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/411"},{"key":"823_CR19","unstructured":"Feuilloley, L., Fraigniaud, P., Hirvonen, J.: A hierarchy of local decision. In: 43rd International Colloquium on Automata, Languages and Programming (ICALP), pp. 118:1\u2013118:15 (2016)"},{"key":"823_CR20","doi-asserted-by":"publisher","unstructured":"Feuilloley, L., Fraigniaud, P., Hirvonen, J., Paz, A., Perry, M.: Redundancy in distributed proofs. In: 32nd International Symposium on Distributed Computing (DISC), LIPIcs, pp. 24:1\u201324:18. Dagstuhl (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.24","DOI":"10.4230\/LIPIcs.DISC.2018.24"},{"key":"823_CR21","unstructured":"Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., R\u00e9mila, \u00c9., Todinca, I.: Local certification of graphs with bounded genus. arXiv:2007.08084 (2020)"},{"key":"823_CR22","doi-asserted-by":"publisher","unstructured":"Feuilloley, L., Hirvonen, J.: Local verification of global proofs. In: 32nd Int. Symp. on Distributed Computing (DISC), LIPIcs 121, pp. 25:1\u201325:17. Dagstuhl (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.25","DOI":"10.4230\/LIPIcs.DISC.2018.25"},{"issue":"5","key":"823_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2499228","volume":"60","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 1\u201326 (2013). https:\/\/doi.org\/10.1145\/2499228","journal-title":"J. ACM"},{"key":"823_CR24","doi-asserted-by":"publisher","unstructured":"Fraigniaud, P., Montealegre, P., Oshman, R., Rapaport, I., Todinca, I.: On distributed Merlin-Arthur decision protocols. In: 26th Int. Colloquium Structural Information and Communication Complexity (SIROCCO), LNCS 11639, pp. 230\u2013245. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-24922-9_16","DOI":"10.1007\/978-3-030-24922-9_16"},{"issue":"3","key":"823_CR25","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s00446-018-0340-8","volume":"32","author":"P Fraigniaud","year":"2019","unstructured":"Fraigniaud, P., Patt-Shamir, B., Perry, M.: Randomized proof-labeling schemes. Distrib. Comput. 32(3), 217\u2013234 (2019). https:\/\/doi.org\/10.1007\/s00446-018-0340-8","journal-title":"Distrib. Comput."},{"issue":"2","key":"823_CR26","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02579375","volume":"5","author":"H de Fraysseix","year":"1985","unstructured":"de Fraysseix, H., Rosenstiehl, P.: A characterization of planar graphs by tr\u00e9maux orders. Combinatorica 5(2), 127\u2013135 (1985). https:\/\/doi.org\/10.1007\/BF02579375","journal-title":"Combinatorica"},{"issue":"1","key":"823_CR27","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1017\/S0963548300001814","volume":"5","author":"Z F\u00fcredi","year":"1996","unstructured":"F\u00fcredi, Z.: An upper bound on Zarankiewicz\u2019problem. Comb. Probab. Comput. 5(1), 29\u201333 (1996)","journal-title":"Comb. Probab. Comput."},{"key":"823_CR28","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks I: planar embedding. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 29\u201338 (2016). https:\/\/doi.org\/10.1145\/2933057.2933109","DOI":"10.1145\/2933057.2933109"},{"key":"823_CR29","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks II: low-congestion shortcuts, MST, and min-cut. In: 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 202\u2013219 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch16","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"823_CR30","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Parter, M.: Near-optimal distributed DFS in planar graphs. In: 31st Int. Symp. on Distributed Computing (DISC), LIPIcs, pp. 21:1\u201321:16. Dagstuhl (2017). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.21","DOI":"10.4230\/LIPIcs.DISC.2017.21"},{"issue":"1","key":"823_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a019","volume":"12","author":"M G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs in distributed computing. Theory Comput. 12(1), 1\u201333 (2016). https:\/\/doi.org\/10.4086\/toc.2016.v012a019","journal-title":"Theory Comput."},{"key":"823_CR32","doi-asserted-by":"publisher","unstructured":"Hilke, M., Lenzen, C., Suomela, J.: Brief announcement: local approximability of minimum dominating set on planar graphs. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 344\u2013346 (2014). https:\/\/doi.org\/10.1145\/2611462.2611504","DOI":"10.1145\/2611462.2611504"},{"issue":"4","key":"823_CR33","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"JE Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549\u2013568 (1974). https:\/\/doi.org\/10.1145\/321850.3218520","journal-title":"J. ACM"},{"key":"823_CR34","doi-asserted-by":"publisher","unstructured":"Itkis, G., Levin, L.A.: Fast and lean self-stabilizing asynchronous protocols. In: 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 226\u2013239 (1994). https:\/\/doi.org\/10.1109\/SFCS.1994.365691","DOI":"10.1109\/SFCS.1994.365691"},{"key":"823_CR35","doi-asserted-by":"publisher","unstructured":"Kol, G., Oshman, R., Saxena, R.R.: Interactive distributed proofs. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 255\u2013264 (2018). https:\/\/doi.org\/10.1016\/S0304-3975(96)00286-11","DOI":"10.1016\/S0304-3975(96)00286-1"},{"issue":"4","key":"823_CR36","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib, Comput. 22(4), 215\u2013233 (2010). https:\/\/doi.org\/10.1007\/s00446-010-0095-3","journal-title":"Distrib,. Comput."},{"key":"823_CR37","doi-asserted-by":"publisher","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 300\u2013309 (2004). https:\/\/doi.org\/10.1145\/1011767.1011811","DOI":"10.1145\/1011767.1011811"},{"key":"823_CR38","doi-asserted-by":"publisher","unstructured":"Lenzen, C., Oswald, Y.A., Wattenhofer, R.: What can be approximated locally?: case study: dominating sets in planar graphs. In: 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 46\u201354 (2008). https:\/\/doi.org\/10.1145\/1378533.1378540","DOI":"10.1145\/1378533.1378540"},{"issue":"2","key":"823_CR39","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s00446-013-0186-z","volume":"26","author":"C Lenzen","year":"2013","unstructured":"Lenzen, C., Pignolet, Y.A., Wattenhofer, R.: Distributed minimum dominating set approximations in restricted families of graphs. Distrib. Comput. 26(2), 119\u2013137 (2013). https:\/\/doi.org\/10.1007\/s00446-013-0186-z","journal-title":"Distrib. Comput."},{"key":"823_CR40","doi-asserted-by":"publisher","unstructured":"Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1096\u2013115 (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.67","DOI":"10.1137\/1.9781611975994.67"},{"key":"823_CR41","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"issue":"5","key":"823_CR42","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D Peleg","year":"2000","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427\u20131442 (2000). https:\/\/doi.org\/10.1137\/S00975397003697404","journal-title":"SIAM J. Comput."},{"key":"823_CR43","doi-asserted-by":"publisher","unstructured":"Roditty, L., Williams, V.V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: 45th ACM Symposium on Theory of Computing (STOC), pp. 515\u2013524 (2013). https:\/\/doi.org\/10.1145\/2488608.2488673","DOI":"10.1145\/2488608.2488673"},{"issue":"5","key":"823_CR44","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"AD Sarma","year":"2012","unstructured":"Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012). https:\/\/doi.org\/10.1016\/S0304-3975(96)00286-15","journal-title":"SIAM J. Comput."},{"issue":"3","key":"823_CR45","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.ipl.2013.11.008","volume":"114","author":"W Wawrzyniak","year":"2014","unstructured":"Wawrzyniak, W.: A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs. Inf. Process. Lett. 114(3), 94\u201398 (2014). https:\/\/doi.org\/10.1016\/j.ipl.2013.11.0086","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00823-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00823-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00823-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T13:18:04Z","timestamp":1672060684000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00823-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,6]]},"references-count":45,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["823"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00823-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,6]]},"assertion":[{"value":"8 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}