论文标题
平面图的双宽度最多是8个，一些相关的界限
Twin-width of Planar Graphs is at most 8, and some Related Bounds
论文作者
论文摘要
双宽度是Bonnet，Kim，Thomassé和Watrigant [focs 2020]引入的结构宽度参数，并且在图和参数化算法中具有有趣的应用。非常简而言之，双宽度的本质是给定图的逐渐减少（收缩序列）降低到一个顶点，同时保持了顶点邻域的有限差异，并且可以被广泛概括为其他几个传统的结构参数。尽管对于许多自然图类别，众所周知，它们的双宽度是有限的，但在非平凡的情况下，在双宽度上发表的上限通常是“天文学上的大型”。 我们专注于平面图，自从引入以来就已经已经界定了双宽度，但是花了一些时间才花了一些时间才能到来。也就是说，按照预印本的外观顺序，它最多是Jacob和Pilipczuk [Arxiv，2022年1月]的183，而Bonnet，Kwon和Wood [Arxiv，2022年2月]的583。随后在2022年的Arxiv手稿将绑定降至37（Bekos等人），11和9（均为Hliněný）。我们进一步阐述了后者手稿中使用的方法，证明每个平面图的双宽度最多是8，并在线性时间内构建了见证收缩序列。请注意，目前最好的下层平面示例是Král和Lamaison [Arxiv，2022年9月]的Twin Width 7。我们还证明了在两部分平面和1平面图（6和16）和地图图（38）的双分宽上的小显式上边界。所有这些结果的共同点是使用一种新型的平面图的专门制作的递归分解，这在其他领域也可能很有用。
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020], and has interesting applications in the areas of logic on graphs and in parameterized algorithmics. Very briefly, the essence of twin-width is in a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. While for many natural graph classes it is known that their twin-width is bounded, published upper bounds on the twin-width in non-trivial cases are very often "astronomically large". We focus on planar graphs, which are known to have bounded twin-width already since the introduction of it, but it took some time for the first explicit "non-astronomical" upper bounds to come. Namely, in the order of preprint appearance, it was the bound of at most 183 by Jacob and Pilipczuk [arXiv, January 2022], and 583 by Bonnet, Kwon and Wood [arXiv, February 2022]. Subsequent arXiv manuscripts in 2022 improved the bound down to 37 (Bekos et al.), 11 and 9 (both by Hliněný). We further elaborate on the approach used in the latter manuscripts, proving that the twin-width of every planar graph is at most 8, and construct a witnessing contraction sequence in linear time. Note that the currently best lower-bound planar example is of twin-width 7, by Král and Lamaison [arXiv, September 2022]. We also prove small explicit upper bounds on the twin-width of bipartite planar and 1-planar graphs (6 and 16), and of map graphs (38). The common denominator of all these results is the use of a novel specially crafted recursive decomposition of planar graphs, which may be found useful also in other areas.
