Bounded-degree planar graphs do not have bounded-degree product structure

DOI10.37236/11712zbMATH Open1548.05281MaRDI QIDQ6574390

David R. Wood, Vida Dujmović, Pat Morin, Piotr Micek, Gwenaël Joret

Publication date: 18 July 2024

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

zbMATH Keywords

planar graphsproduct structure

Mathematics Subject Classification ID

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

Cites Work

• On tree-partition-width
• An improved planar graph product structure theorem
• Graph minors. II. Algorithmic aspects of tree-width
• Some results on tree decomposition of graphs
• Planar Graphs Have Bounded Queue-Number
• Improved Bounds for Centered Colorings
• The intrinsic dimensionality of graphs
• Improved product structure for graphs on surfaces
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• The product structure of squaregraphs
• Graph product structure for non-minor-closed classes
• An Optimal Algorithm for Product Structure in Planar Graphs

This page was built for publication: Bounded-degree planar graphs do not have bounded-degree product structure