An improved planar graph product structure theorem
From MaRDI portal
Summary: \textit{V. Dujmović} et al. [J. ACM 67, No. 4, Article No. 22, 38 p. (2020; Zbl 1466.05047)] proved that for every planar graph \(G\) there is a graph \(H\) with treewidth at most 8 and a path \(P\) such that \(G\subseteq H\boxtimes P\). We improve this result by replacing ``treewidth at most 8 by ``simple treewidth at most 6.
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
- 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
- scientific article; zbMATH DE number 1944139 (Why is no real title available?)
- 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
(26)- scientific article; zbMATH DE number 2192094 (Why is no real title available?)
- Shorter Labeling Schemes for Planar Graphs
- Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
- Sparse universal graphs for planarity
- Shallow Minors, Graph Products, and Beyond-Planar Graphs
- The product structure of squaregraphs
- Graph product structure for non-minor-closed classes
- Linear layouts of bipartite planar graphs
- An improved planar graph product structure theorem
- Product structure extension of the Alon-Seymour-Thomas theorem
- Bounded-degree planar graphs do not have bounded-degree product structure
- Colouring strong products
- Product structure of graph classes with bounded treewidth
- Product structure of graph classes with bounded treewidth
- Product structure of graphs with an excluded minor
- Graph product structure for \(h\)-framed graphs
- Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
- On the complexity of embedding in graph products
- Intersection graphs with and without product structure
- Product structure of graph classes with strongly sublinear separators
- Grid minors and products
- Treewidth 2 in the planar graph product structure theorem
- Structural properties of graph products
- Powers of planar graphs, product structure, and blocking partitions (extended abstract)
- \(\mathcal{H}\)-clique-width and a hereditary analogue of product structure
- Twin-width of graphs on surfaces
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)
