An improved planar graph product structure theorem

DOI10.37236/10614MaRDI QIDQ2152790zbMATH OpenOpenAlexWikidataFDO

Authors Torsten Ueckerdt, David R. Wood, Wendy Yi

Publication date 11 July 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2108.00198

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Graph product structure for non-minor-closed classes
• Notes on graph product structure theory
• A fast algorithm for the product structure of planar graphs
• Quickly excluding a planar graph
• Treewidth of Cartesian products of highly connected graphs
• Graph minors. III. Planar tree-width
• On the path-width of planar graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Subgraph Isomorphism in Planar Graphs and Related Problems
• On the frequency of 3-connected subgraphs of planar graphs

Cites work

• scientific article; zbMATH DE number 1944139 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Adjacency Labelling for Planar Graphs (and Beyond)
• Apollonian ball packings and stacked polytopes
• Characterization and Recognition of Partial 3-Trees
• Clustered 3-colouring graphs of bounded degree
• Graph minors. II. Algorithmic aspects of tree-width
• Graphs on surfaces
• Improved bounds for centered colorings
• Parameters tied to treewidth
• Planar graphs have bounded nonrepetitive chromatic number
• Planar graphs have bounded queue-number
• Proofs from THE BOOK
• Separating layered treewidth and row treewidth
• Shorter Labeling Schemes for Planar Graphs
• Some properties of random Apollonian networks
• Subclasses of \(k\)-trees: characterization and recognition

Cited in

(16)

• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• The product structure of squaregraphs
• Product structure of graph classes with bounded treewidth
• Product structure extension of the Alon-Seymour-Thomas theorem
• Bounded-degree planar graphs do not have bounded-degree product structure
• Graph product structure for non-minor-closed classes
• Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
• scientific article; zbMATH DE number 2192094 (Why is no real title available?)
• Linear layouts of bipartite planar graphs
• Colouring strong products
• Shorter Labeling Schemes for Planar Graphs
• Product structure of graph classes with bounded treewidth
• An improved planar graph product structure theorem
• Product structure of graphs with an excluded minor
• Sparse universal graphs for planarity
• Graph product structure for \(h\)-framed graphs

This page was built for publication: An improved planar graph product structure theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2152790)