Answers are grounded in this paper and cite their sources.
We introduce, for every surface $Σ$, a two-way connection between definability of a graph class C by FO transductions (first-order logical transformations) of the graphs embeddable in $Σ$ and a certain variant of fan-crossing drawings of the graphs from C in $Σ$. If C is additionally of bounded maximum degree, then the restriction on drawings of the graphs from C in $Σ$ is simply to have a bounded number of crossings per edge (such as being k-planar for fixed~k if $Σ$ is the plane). For graph classes, this connection allows us to derive non-transducibility results from the nonexistence of the said drawings and, conversely, from the nonexistence of a transduction to derive nonexistence of the said drawings. One example of such reasoning is as follows; since the class of 3D-grids is not transducible from the class of planar graphs, we can conclude that the class of 3D-grids is not k-planar for any fixed~k. On the other hand, the fact that the class of 3D-grids is not k-planar for any fixed~k is known also via other means, and this conversely implies that the class of 3D-grids is not transducible from the class of planar graphs. 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. The result is based on a recent characterization of weakly sparse FO transductions of classes of bounded expansion by [Gajarský, Gładkowski, Jedelský, Pilipczuk and Toruńczyk, arXiv:2505.15655].
No takes yet. Share an insight, caveat, or question.
Hliněný et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: