Transductions of Graph Classes Admitting Product Structure
| Authors | |
|---|---|
| Year of publication | 2025 |
| Type | Article in Proceedings |
| Conference | 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
| MU Faculty or unit | |
| Citation | |
| web | arXiv |
| Doi | https://doi.org/10.1109/LICS65433.2025.00069 |
| Keywords | product structure; hereditary class; clique-width; transduction |
| Description | 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 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. |
| Related projects: |