Notes on graph product structure theory
From MaRDI portal
Abstract: It was recently proved that every planar graph is a subgraph of the strong product of a path and a graph with bounded treewidth. This paper surveys generalisations of this result for graphs on surfaces, minor-closed classes, various non-minor-closed classes, and graph classes with polynomial growth. We then explore how graph product structure might be applicable to more broadly defined graph classes. In particular, we characterise when a graph class defined by a cartesian or strong product has bounded or polynomial expansion. We then explore graph product structure theorems for various geometrically defined graph classes, and present several open problems.
Recommendations
Cites work
- A partial k-arboretum of graphs with bounded treewidth
- A Separator Theorem for Planar Graphs
- A separator theorem for string graphs and its applications
- Applications of a new separator theorem for string graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Bounded-degree graphs have arbitrarily large queue-number
- Characterisations and examples of graph classes with bounded expansion
- Clique minors in Cartesian products of graphs
- Coloring and covering nowhere dense graphs
- Colouring graphs with bounded generalized colouring number
- Comparing Queues and Stacks As Machines for Laying Out Graphs
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. XVI: Excluding a non-planar graph
- Graph theory
- Graphs on surfaces
- scientific article; zbMATH DE number 1003278 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1057879 (Why is no real title available?)
- scientific article; zbMATH DE number 1944139 (Why is no real title available?)
- scientific article; zbMATH DE number 6297748 (Why is no real title available?)
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
- Implicat Representation of Graphs
- Improved bounds for centered colorings
- Map graphs
- Minor-Closed Graph Classes with Bounded Layered Pathwidth
- Multiple-source shortest paths in embedded graphs
- Nonrepetitive colorings of graphs
- On classes of graphs with strongly sublinear separators
- On the generalised colouring numbers of graphs that exclude a fixed minor
- On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
- On tree-partition-width
- Orderings on graphs and game coloring number
- Parameters tied to treewidth
- Planar graphs have bounded queue-number
- Polynomial expansion and sublinear separators
- Recognizing string graphs is decidable
- Separators for sphere-packings and nearest neighbor graphs
- Shorter Labeling Schemes for Planar Graphs
- Some results on tree decomposition of graphs
- Sparsity. Graphs, structures, and algorithms
- Strongly sublinear separators and polynomial expansion
- Structure of graphs with locally restricted crossings
- Sublinear separators, fragility and subexponential expansion
- The intrinsic dimensionality of graphs
- Treewidth of graphs with balanced separations
- Two lower bounds for p-centered colorings
Cited in
(22)- Unification of graph products and compatibility with switching
- Improved bounds for weak coloring numbers
- Stack-number is not bounded by queue-number
- An improved planar graph product structure theorem
- A fast algorithm for the product structure of planar graphs
- Shorter Labeling Schemes for Planar Graphs
- Note on strong product graph dimension
- Separating layered treewidth and row treewidth
- Shallow Minors, Graph Products, and Beyond-Planar Graphs
- The product structure of squaregraphs
- Graph product structure for non-minor-closed classes
- Bounded-degree planar graphs do not have bounded-degree product structure
- Planar graph with twin-width seven
- Product structure of graph classes with bounded treewidth
- Product structure of graphs with an excluded minor
- Graph product structure for \(h\)-framed graphs
- On the complexity of embedding in graph products
- Intersection graphs with and without product structure
- Structural properties of graph products
- Pliability and approximating Max-CSPs
- \(\mathcal{H}\)-clique-width and a hereditary analogue of product structure
- Twin-width of graphs on surfaces
This page was built for publication: Notes on graph product structure theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2058955)
