[gt.go] - "Smaller Universal Graphs for Caterpillars and Graphs of Bounded Path-Width (part 2)" by Cyril Gavoille
/Exposé en français/Talk in french / Transparents en anglais/English slides/
In this talk, I will given a rather simple construction of a graph U n with at most 8n vertices with the property that every n-vertex caterpillar is isomorphic to some induced-subgraph of U n . Previous constructions of so-called induced-universal graph for caterpillars used 256n vertices in the best (Bonichon et al. SIROCCO'06 and Alstrup et al. FOCS'15).
Then, I will also present an extension to path-width-p graphs with an induced-universal graph of n.2 O(p) vertices. This is complemented with a n.2 Ω(p) lower bound. With bounded path-width graphs, our
construction considerably enlarge the family of n-vertex graphs having an induced-universal graph of O(n) vertices, which is optimal. Such unexpected property was known only for trees, bounded maximum degree outerplanar graphs and maximum degree-2 graphs.
The extended result is obtained from an algorithmic approach by designing an adjacency labeling scheme for these graphs using log(n) + O(p) bit vertex labels and with a constant time adjacency test.
This is a joint work with Arnaud Labourel.
[Cyril Gavoille] (Université de Bordeaux )
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .