/Exposé en français/Talk in french / English slides / transparents en anglais

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 with Arnaud Labourel.

[Cyril Gavoille] (Université de Bordeaux, Labri )

https://dept-info.labri.fr/~gavoille/

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 ] .