一句话：证明 3D-grid 类不能从平面图及任何有界亏格图类转导得到，并提出切片分解这一新结构工具。
论文研究图类之间的单子二阶转导能力，目标是证明 3D-grid 类不能从平面图转导得到，并推广到任何有界亏格图类。作者引入新的结构工具——切片分解（slice decompositions），并证明：若某图类可由有界亏格图类转导，则它是有切片分解图类的扰动；此外，边稳定且具有切片分解的图类可从具有切片分解的弱稀疏图类转导得到。这些结果刻画了有界亏格图在转导下的结构极限，并由此给出 3D-grid 不可从平面图或有界亏格图类转导得到的证明。
We prove that the class of 3D-grids cannot be transduced from planar graphs, and more generally, from any class of graphs of bounded genus. To prove our result, we introduce a new structural tool called slice decompositions and study its properties. We show that every graph class transducible from a class of graphs of bounded genus is a perturbation of a graph class that admits slice decompositions. Moreover, we show that edge-stable graph classes that admit slice decomposition are transducible from weakly sparse graph classes that admits slice decompositions.
DOI 原文 ·
@inproceedings{paperbot8633,
title = {3D-grids are not transducible from planar graphs},
author = {Jakub Gajarský and Michał Pilipczuk and Filip Pokrývka},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00068}
}