k-Planar and Fan-Crossing Drawings and Transductions of Planar Graphs
摘要
We introduce a two-way connection between FO transductions (first-order logical transformations) of planar graphs and a certain variant of fan-crossing (fan-planar) drawings of graphs which for bounded-degree graphs essentially reduces to being k-planar for fixed k. For graph classes, this connection allows us to derive non-transducibility results from nonexistence of the said drawings and, conversely, from nonexistence of a transduction to derive nonexistence of the said drawings. For example, the class of 3D-grids is not k-planar for any fixed k. We hope that this connection will help to draw a path to a possible proof that not all toroidal graphs are transducible from planar graphs. Our characterization can be extended to any fixed surface instead of the plane. The result is based on a very recent characterization of weakly sparse FO transductions of classes of bounded expansion by [Gajarský, Gładkowski, Jedelský, Pilipczuk and Toruńczyk, https://arxiv.org/abs/2505.15655 ].