一句话：证明乘积结构图类的一阶转导可由 H-clique-width 刻画，并据此分离 3D 网格与平面图。
本文研究遗传图类的一阶转导层级，特别关注平面图等具乘积结构图类的一阶转导具有何种性质。作者采用 Dujmović 等人引入的乘积结构概念（路径与有界树宽图的强积的子图），证明：若图类可由具乘积结构的图类一阶转导得到，则在扰动意义下也满足一种推广乘积结构的稠密遗传刻画，即作者最近提出的 H-clique-width。基于该刻画，他们证明 3D 网格以及某类 2D 网格变形不能从具乘积结构的图类一阶转导得到，特别不能从平面图类一阶转导得到。该结果推进了对一阶转导层级的理解，并给出新的不可转导实例。
In a quest to thoroughly understand the first-order transduction hierarchy of hereditary graph classes, some questions in particular stand out; such as, what properties hold for graph classes that are first-order transductions of planar graphs (and of similar classes)? When addressing this (so-far wide open) question, we turn to the concept of a product structure – being a subgraph of the strong product of a path and a graph of bounded tree-width, introduced by Dujmović et al. [JACM 2020]. Namely, we prove that any graph class which is a first-order transduction of a class admitting such product structure, up to perturbations also meets a structural description generalizing the concept of a product structure in a dense hereditary way—the latter concept being introduced just recently by authors under the name of $\mathcal{H}$-clique-width [MFCS 2024].Using this characterization, we show that the class of the 3D grids, as well as a class of certain modifications of 2D grids, are not first-order transducible from classes admitting a product structure, and in particular not from the class of planar graphs.
DOI 原文 ·
@inproceedings{paperbot8629,
title = {Transductions of Graph Classes Admitting Product Structure},
author = {Petr Hliněný and Jan Jedelský},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00069}
}