EUVIMEDEUVIMED entdecken
Crossref

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

Petr Hliněný, Jan Jedelský

Discrete Mathematics & Theoretical Computer Science · 16.11.2026 · vol. 28:4, SOFSEM 2026 (Special issues)

DOI: 10.46298/dmtcs.17710 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 16.11.2026. Verfasst von Petr Hliněný und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce, for every surface $Σ$, a two-way connection between definability of a graph class $\mathcal 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 $\mathcal C$ in $Σ$. If $\mathcal C$ is additionally of bounded maximum degree, then the restriction on drawings of the graphs from $\mathcal 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].

Zitieren

APA

Hliněný, P., & Jedelský, J. (2026). k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs. Discrete Mathematics & Theoretical Computer Science, vol. 28:4, SOFSEM 2026(Special issues). https://doi.org/10.46298/dmtcs.17710

Vancouver

Hliněný P, Jedelský J. k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:4, SOFSEM 2026(Special issues). doi:10.46298/dmtcs.17710

BibTeX
@article{Hlinn2026,
  author = {Hliněný, Petr and Jedelský, Jan},
  title = {k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs},
  journal = {Discrete Mathematics & Theoretical Computer Science},
  year = {2026},
  volume = {vol. 28:4, SOFSEM 2026},
  number = {Special issues},
  doi = {10.46298/dmtcs.17710}
}
Kostenlos starten →