English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Twin-width is a structural width parameter introduced by Bonnet, Kim,Thomass\'e and Watrigant [FOCS 2020], and has interesting applications in theareas of logic on graphs and in parameterized algorithmics. Very briefly, theessence of twin-width is in a gradual reduction (a contraction sequence) of thegiven graph down to a single vertex while maintaining limited difference ofneighbourhoods of the vertices, and it can be seen as widely generalizingseveral other traditional structural parameters. While for many natural graphclasses it is known that their twin-width is bounded, published upper bounds onthe twin-width in non-trivial cases are very often "astronomically large".  We focus on planar graphs, which are known to have bounded twin-width alreadysince the introduction of it, but it took some time for the first explicit"non-astronomical" upper bounds to come. Namely, in the order of preprintappearance, 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 etal.), 11 and 9 (both by Hlin\v{e}n\'y). We further elaborate on the approachused in the latter manuscripts, proving that the twin-width of every planargraph is at most 8, and construct a witnessing contraction sequence in lineartime. Note that the currently best lower-bound planar example is of twin-width7, by Kr\'al and Lamaison [arXiv, September 2022]. We also prove small explicitupper bounds on the twin-width of bipartite planar and 1-planar graphs (6 and16), and of map graphs (38). The common denominator of all these results is theuse of a novel specially crafted recursive decomposition of planar graphs,which may be found useful also in other areas.

Twin-width of Planar Graphs is at most 8, and some Related Bounds