Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
share
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),9/2bw(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 |X|=n is n - log_2(n) + 𝒪(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.
READ FULL TEXT