Compact local certification of graph classes

There are more and more distributed algorithms specially designed to work on specific graph classes, such as interval graphs or planar graphs. Before running such algorithms, one would like to be sure that the graph does belong to the class. In this talk, we tackle the problem of locally certifying graph classes.  Specifically, we explain recent results showing the design compact certification (i.e. proof-labeling schemes with logarithmic certificates) for planar, bounded genus, chordal, interval, circular-arc, permutation and bounded treewidth graphs.

 Vía Zoom.