k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs
This work addresses theoretical graph drawing and logic transductions for researchers in computational geometry and graph theory, offering a novel framework but incremental in building on recent characterizations.
The paper establishes a connection between FO transductions of graphs embeddable in surfaces and fan-crossing drawings, enabling non-transducibility proofs from drawing constraints and vice versa, as demonstrated for 3D-grids not being k-planar for any fixed k.
We introduce, for every surface Σ, a two-way connection between FO transductions (first-order logical transformations) of the graphs embeddable in Σ and a certain variant of fan-crossing drawings of graphs in Σ. If the target graphs drawn in Σ are additionally of bounded maximum degree, then the restriction on drawings 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 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. 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, arXiv:2505.15655].