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

The planar graph product structure theorem of Dujmovi\'{c}, Joret, Micek,Morin, Ueckerdt, and Wood [J. ACM 2020] states that every planar graph is asubgraph of the strong product of a graph with bounded treewidth and a path.This result has been the key tool to resolve important open problems regardingqueue layouts, nonrepetitive colourings, centered colourings, and adjacencylabelling schemes. In this paper, we extend this line of research by utilizingshallow minors to prove analogous product structure theorems for several beyondplanar graph classes. The key observation that drives our work is that manybeyond planar graphs can be described as a shallow minor of the strong productof a planar graph with a small complete graph. In particular, we show thatpowers of planar graphs, $k$-planar, $(k,p)$-cluster planar, fan-planar and$k$-fan-bundle planar graphs have such a shallow-minor structure. Using acombination of old and new results, we deduce that these classes have boundedqueue-number, bounded nonrepetitive chromatic number, polynomial $p$-centredchromatic numbers, linear strong colouring numbers, and cubic weak colouringnumbers. In addition, we show that $k$-gap planar graphs have at leastexponential local treewidth and, as a consequence, cannot be described as asubgraph of the strong product of a graph with bounded treewidth and a path.

Shallow Minors, Graph Products and Beyond Planar Graphs