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

We prove that the $k$-power of any planar graph $G$ is contained in$H\boxtimes P\boxtimes K_{f(\Delta(G),k)}$ for some graph $H$ with treewidth$15\,288\,899$, some path $P$, and some function $f$. This resolves an openproblem of Ossona de Mendez. In fact, we prove a more general result in termsof shallow minors that implies similar results for many `beyond planar' graphclasses, without dependence on $\Delta(G)$. For example, we prove that every$k$-planar graph is contained in $H\boxtimes P\boxtimes K_{f(k)}$ for somegraph $H$ with treewidth $15\,288\,899$ and some path $P$, and some function$f$. This resolves an open problem of Dujmovi\'c, Morin and Wood. We generaliseall these results for graphs of bounded Euler genus, still with an absolutebound on the treewidth.  At the heart of our proof is the following new concept of independentinterest. An $\ell$-blocking partition of a graph $G$ is a partition of $V(G)$into connected sets such that every path of length greater than $\ell$ in $G$contains at least two vertices in one part. We prove that every graph of Eulergenus $g$ has a $894$-blocking partition with parts of size bounded by afunction of $\Delta(G)$ and $g$. Motivated by this result, we study blockingpartitions in their own right. We show that every graph has a $2$-blockingpartition with parts of size bounded by a function of $\Delta(G)$ and$\textrm{tw}(G)$. On the other hand, we show that 4-regular graphs do not have$\ell$-blocking partitions with bounded size parts.

Powers of planar graphs, product structure, and blocking partitions