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

*Algorithmica*. 2021.

doi:10.1007/s00453-021-00823-w.

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.