论文标题
图表结构理论的注释
Notes on Graph Product Structure Theory
论文作者
论文摘要
最近证明，每个平面图都是路径强产物的子图和具有界面宽度的图形。本文调查了该结果的概括，以表面上的图，次要类别，各种非限制类别以及具有多项式生长的图形类别。然后，我们探索图形产品结构如何适用于更广泛定义的图形类。特别是，我们表征何时由笛卡尔或强产物定义的图形类具有界定或多项式扩展。然后，我们探索各种几何定义的图形类别的图形产品结构定理，并提出几个开放问题。
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.
