The structural parameter twin-width was introduced by Bonnet et al. in [FOCS 2020], and already this first paper included an asymptotic argument bounding the twin-width of planar graphs by a non-explicit constant. Quite recently, we have seen first small explicit upper bounds of 183 by Jacob and Pilipczuk [arXiv, January 2022, also WG'22], 583 by Bonnet et al. [arXiv, February 2022], of 37 by Bekos et al. [arXiv, April 2022], and of 9 by the first author [arXiv, June 2022]. We further elaborate on the approach used in the last paper and improve the upper bound to 8. This is already very close to the currently best lower bound of 7 by Kr\'al and Lamaison [arXiv,September 2022].
翻译：Bonnet等人在[FOCS 2020] 中提出了结构参数双边,这第一份论文已经包括了用一个非明白的常数将平面图的双边捆绑在一起的无症状论据。 就在最近,我们第一次看到Jacob和Pilipczuk[2022年1月,arXiv, 也是WG'22]、Bonnet等人[2022年2月,arXiv]、Bekos等人[2022年2月,]、Bekos等人[2022年4月,arXiv]37和9名第一作者[2022年6月,arXiv]的183个小明显上边线。我们进一步阐述了上边页使用的方法,并将上边线改进为8。 这已经非常接近Kr\al和Lamaison[2022年9月,ArXiv,2022年9月)目前最低的7个下边框。
相关内容
微信扫码咨询专知VIP会员