Local certification of planarity

Speaker: Laurent Feuilloley (Université du Chili)

Abstract: In this talk I will introduce the notion of local certification and describe the approach of a recent paper for certifying planarity.

Local certification is a kind of analogue of NP (for graph problems), where the decision is not taken by an external algorithm, but by the nodes of the graph themselves. Every node is given a label by a prover, and has to take a local decision (accept or reject) based on this label and the labels of its neighbors. The graph is accepted if and only if all nodes accept.

The mechanism originates from the study of fault-tolerance in distributed computing, but is an interesting concept in itself. In particular the size of the labels can be considered as measure of the locality of the class we want to certify.

For certifying planarity, our approach consists basically in (virtually) transforming the graph into an outerplanar graph by duplicating some nodes of a spanning tree, and then to use the ordering of the nodes around the outerface as a labeling.

The talk assumes no knowledge except for basic graph notions. The paper is here: https://arxiv.org/abs/2005.05863. It is joint work with Pierre Fraigniaud, Ivan Rapaport, Éric Rémila, Pedro Montealegre and Ioan Todinca.

Date and time: 18/06/2020 at 14:30 (UTC+2)

Link to the videoconference server: https://bbb-temp.grenet.fr/b/lou-9x7-69p

Slides: 18-06-2020_slides_feuilloley.pdf