Résumé
Twin-width is a newly introduced graph width parameter that aims at generalizing a wide range of "nicely structured" graph classes. In this work, we focus on obtaining good bounds on twin-width tww(G) for graphs G from a number of classic graph classes. We prove the following:
- tww(G) <= 3 . 2(tw(G)-1), where tw (G) is the treewidth of G,
- tww(G) <= max(4bw(G), 4bw(G), 9/2 bw (G) - 3) for a planar graph G with bw(G) >= 2, where bw(G) is the branchwidth of G,
- tww(G) <= 183 for a planar graph G,
- the twin-width of a universal bipartite graph (X, 2(X), E) with vertical bar X vertical bar = n is n - log(2) (n) + O(1).
An important idea behind the bounds for planar graphs is to use an embedding of the graph and sphere-cut decompositions to obtain good bounds on neighbourhood complexity.