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

Petr Hliněný, Jan Jedelský

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…