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 ].

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

k-Planar and Fan-Crossing Drawings and Transductions of Planar Graphs

  • Petr Hliněný,
  • Jan Jedelský

摘要

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 ].