View PDF HTML (experimental)

Abstract:We introduce, for every surface $\Sigma$, a two-way connection between definability of a graph class $\mathcal C$ by FO transductions (first-order logical transformations) of the graphs embeddable in $\Sigma$ and a certain variant of fan-crossing drawings of the graphs from $\mathcal C$ in $\Sigma$. If the considered class $\mathcal C$ is additionally of bounded maximum degree, then the restriction on drawings of the graphs from $\mathcal C$ in $\Sigma$ is simply to have a bounded number of crossings per edge (such as being $k$-planar for fixed~$k$ if $\Sigma$ 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 derive 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].

Submission history

From: Jan Jedelský [view email]
[v1] Tue, 10 Jun 2025 08:54:08 UTC (34 KB)
[v2] Thu, 18 Sep 2025 19:12:56 UTC (32 KB)
[v3] Thu, 12 Mar 2026 13:39:59 UTC (27 KB)
[v4] Mon, 29 Jun 2026 16:44:21 UTC (45 KB)