论文标题
有界树的界限，平面图和两部分图
Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
论文作者
论文摘要
Twin Width是一个新引入的图形宽度参数，旨在概括一系列“结构化”的图形类。在这项工作中，我们专注于从许多经典图类别中的Graphs $ G $中获得twin宽度$ \ text {tww}（g）$的良好界限。我们证明了以下内容： - $ \ text {tww}（g）\ leq 3 \ cdot 2^{\ text {tw}（g）（g）-1} $，其中$ \ text {tw}（g）$是$ g $的树宽， - $ \ text {tww}（g）\ leq \ max（4 \ text {bw}（g），\ frac {9} {2} {2} \ text {bw}（g）-3）$ g $ g $ g $ g $，带有$ \ text {bw}（bw}（bw}（g）$ geq 2 $， $ g $， - $ \ text {tww}（g）\ leq 183 $ for Planar Graph $ g $， - 带有$ | x | = n $ is $ n- \ log_2（n） + \ Mathcal {O}（1）$。 平面图的边界背后的一个重要想法是使用图形和切割分解的嵌入来获得邻里复杂性的良好界限。
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 $\text{tww}(G)$ for graphs $G$ from a number of classic graph classes. We prove the following: - $\text{tww}(G) \leq 3\cdot 2^{\text{tw}(G)-1}$, where $\text{tw}(G)$ is the treewidth of $G$, - $\text{tww}(G) \leq \max(4\text{bw}(G),\frac{9}{2}\text{bw}(G)-3)$ for a planar graph $G$ with $\text{bw}(G) \geq 2$, where $\text{bw}(G)$ is the branchwidth of $G$, - $\text{tww}(G) \leq 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) + \mathcal{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.
