30 citations · 52 across the 10 of their papers we have counts for
5 papers · 1 filter
Adjacency Labelling for Planar Graphs (and Beyond)
Vida Dujmović, Louis Esperet, Gwenaël Joret +3
We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an -vertex planar graph is assigned a -bit label and the lab…
Shorter Labeling Schemes for Planar Graphs
Marthe Bonamy, Cyril Gavoille, Michal Pilipczuk
An \emph{adjacency labeling scheme} for a given class of graphs is an algorithm that for every graph from the class, assigns bit strings (labels) to vertices of so that for…
Simpler, faster and shorter labels for distances in graphs
Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen +1
We consider how to assign labels to any undirected graph with n nodes such that, given the labels of two nodes and no other information regarding the graph, it is possible to deter…
Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
Ittai Abraham, Cyril Gavoille, Anupam Gupta +2
We prove that any graph excluding as a minor has can be partitioned into clusters of diameter at most while removing at most fraction of the edges. This improves…
Compact Labelings For Efficient First-Order Model-Checking
Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté
We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checki…