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

arXiv:2506.08585 · cs.CG, cs.LO, math.CO · Submitted 2025-06-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs".

Title and authors: Jane: Let's talk about who wrote this. Petr Hlinen and Jan Jedelský are the authors, and they’ve put forward this concept of connecting FO transductions and fan-crossing drawings in their paper, "k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs."

Tom: They’re linking definability by first-order logic transformations to topological properties of how graphs can be drawn on surfaces. It’s a big step because it bridges the gap between pure logic and geometric representation.

Lu: The authors use this connection to characterize classes, especially for bounded maximum degree graphs, linking them to congestion depth minors and fan-crossing drawings in a way that relies on recent work about weakly sparse FO transductions.

Meng: Bounded maximum degree sounds practical because we deal with things that have limits on how connected they can get. What does this mean for the actual graphs we deploy?

Tom: It means if you have a class of bounded maximum degree graphs, you can characterize their transducibility by checking if every graph in that class has a specific type of fan-crossing drawing on some surface Σ after deleting a small number of vertices.

Jane: That sounds like a very concrete condition. So, the paper suggests that for these bounded degree classes, we don't need to check every possible graph; we just need to check the existence of this drawing property.

Lu: Right. The main result they prove is that a class D is transducible from C if and only if there exists some integer k such that every graph in D has a monotone k-fold k-clustered fan-crossing drawing on some surface Σ after deleting at most k vertices.

Meng: Okay, so we can use this drawing property as a test for whether one graph class is logically richer than another. That’s a measurable condition.

Tom: It’s measurable because it depends on the parameter k, which relates to how many times you can cluster and delete vertices. This ties the algebraic notion of transducibility directly to geometric properties in a surface Σ.

Jane: So, if we want to know if a class is transducible, we look for this drawing condition instead of doing some complicated logical transformation on every graph individually.

The paper's summary: Tom: The paper summarizes how they use the simple one-dimensional first-order interpretation of graphs—a binary formula—to define a non-copying FO transduction. This transduction maps a graph G to a set of graphs τ(G), where H is in that set if it’s an induced subgraph of some version of G with colored vertices.

Lu: The paper illustrates this with an example, like taking the subdivided K5 and applying this specific interpretation formula ξ to see how it generates all graphs on less than or equal to n vertices as induced subgraphs.

Meng: So they are using these logical transformations to show how a class can generate a whole family of smaller graphs. That's pretty powerful for understanding what’s possible within that logical framework.

Jane: The core idea is that if you have this transduction, it tells you something about the structure of the graph class D relative to the class C it transducibly from. It shows how one can use these logical tools to map structural properties onto geometric ones.

Tom: They connect this idea to theorems about bounded expansion classes, showing that if D is weakly sparse and transducible from C, then D must be contained in the class of congestion k depth k minors of C for some fixed integer k.

Lu: That’s a characterization result derived from Gajarsky et al.'s work on weakly sparse FO transductions, which connects the algebraic definition to these topological properties like fan-crossing drawings.

Meng: So they're using this to prove that if you have a certain logical structure, you can find a corresponding geometric structure. That’s kind of an elegant way to connect the two fields.

Jane: It suggests that understanding the logic of graph classes is deeply intertwined with how those graphs are embedded in surfaces.

The paper's improvements: Tom: They introduce a key result, Theorem five which states the main finding: a class D is transducible from C if and only if there exists some integer k such that every graph in D has a monotone k-fold k-clustered fan-crossing drawing on some surface Σ after deleting at most k vertices.

Lu: That’s the "if and only if" statement, which is the main result they are building everything around. It turns the property of transducibility into a very concrete, geometric drawing condition.

Meng: So, this means we can test for transducibility by checking for this specific drawing condition instead of doing some abstract logical work on transductions. That’s a huge practical improvement if it's true and scalable.

Jane: If that holds, then determining transducibility is equivalent to finding this drawing structure in a surface Σ after deleting at most k vertices. That makes the problem much more tangible for someone who isn't reading the logic behind FO transductions.

Tom: They also have a corollary that simplifies this even further for classes of bounded maximum degree, showing that transducibility from C is equivalent to having a k-crossing drawing after deleting at most k edges.

Lu: That corollary shows how the main result simplifies when you add the restriction of bounded maximum degree, relating it to simpler crossing numbers on a surface Σ.

Meng: So for bounded degree graphs, we get a direct measure using crossing number properties, which is much easier to compute than checking arbitrary transductions.

Conclusion: Jane: So where does this leave us? The authors conclude that this framework provides a way to move from the abstract idea of FO transductions to concrete geometric drawing constraints.

Tom: It moves the abstract idea of transducibility into something we can verify geometrically, and it sets up a clear path for future research, like exploring connections between different types of drawings or looking at strictly k-fold fan-crossing drawings.

Lu: They also point toward open problems, like whether the class of toroidal graphs is transducible from planar graphs and questions about k-planar embeddings for bounded degree toroidal graphs.

Meng: I’m curious if this geometric approach can be applied to the other problems we have, like those related to three dee-grids or those classes of toroidal graphs <ref:2506.08585#pg3>.

Lalam: From my perspective, this is a strong result because it provides a concrete mechanism for linking logic and geometry in this domain. It gives us something tangible to work with.

Tom: Absolutely. The full title of "k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs" shows how powerful this connection is being applied across different areas of graph theory right now.

Petr Hlinenď y, Jan Jedelskľ y

Masaryk University

cs.CG, cs.LO, math.CO

Submitted: 2025-06-10

Updated: 2026-09-10

Journal ref: Discrete Mathematics & Theoretical Computer Science, vol. 28:4, SOFSEM 2026, Special issues (November 16, 2026) dmtcs:17710

DOI: 10.46298/dmtcs.17710

License: http://creativecommons.org/licenses/by-sa/4.0/

Importance score: 91/100

The gist: k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs introduces a two-way connection between definability of a graph class by FO transductions of embeddable graphs and a certain…

Key concepts

Transduction Hierarchy
This is a way to rank graph classes based on whether one class can be mapped into another using a specific type of logic formula. A class D is transducible from C if there's a mapping that turns graphs in C into graphs in D, creating an ordered structure for these classes.
Fan-Crossing Drawing
This refers to a specific geometric way to draw a graph on a surface where edges cross each other. The paper uses these drawings as algebraic tools; the existence or non-existence of such drawings is linked directly to whether one graph class can be logically transformed into another.
Bounded Expansion
This describes a property of a graph class where every subgraph has limited complexity related to its structure, often measured by how much the graph 'expands' when adding vertices. This property is important because it allows for specific structural bounds on transducibility using minor concepts.
k-Planar/k-Crossing Drawing
These are geometric constraints on how a graph can be drawn on a surface, limiting the number of crossings or the complexity of embedding. The paper uses these drawing limits to characterize and prove properties about graph classes, such as showing that 3D-grids cannot be k-planar for any fixed k.

Terminology

Summary

k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs introduces a two-way connection between definability of a graph class by FO transductions of embeddable graphs and a certain variant of fan-crossing drawings. p. 0

Where the paper says it

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

This connection allows for deriving non-transducibility results from the nonexistence of said drawings and vice versa, which is useful for drawing paths to possible proofs regarding transducibility between graph classes. p. 0
Where the paper says it

If C is additionally of bounded maximum degree, then the restriction on drawings of the graphs from 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.

Transduction Hierarchy and Graph Classes

The paper defines a simple 1-dimensional first-order (FO) interpretation of graphs using a binary FO formula. A non-copying FO transduction maps a graph G to a set of graphs τ(G) such that H ∈ τ(G) if and only if, for some vertex-coloring G+, the graph H is an induced subgraph of ξ(G+). p. 5

Where the paper says it

Transductions. A non-copying transduction τ (determined by a symmetric binary FO formula ξ) maps a graph G to a set of graphs τ (G) such that H ∈ τ (G) if and only if, for some vertex-coloring G+ of G, the graph H is an induced subgraph of ξ(G+).

A class D is transducible from a class C if there is a transduction τ such that D ⊆ τ(C). p. 0
Where the paper says it

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.

The transduction hierarchy is the quasi-order on graph classes given by the transducibility relation. p. 1
Where the paper says it

We defer further discussion on this topic to Section 2. As such, the transduction hierarchy – the quasi-order on graph classes given by the transducibility relation – is of particular interest.

Characterization of Transducibility

Theorem 3 provides a characterization for graph classes of bounded expansion. It states that if D is a graph class transducible from C such that D is weakly sparse, then there exists a k ∈ N such that D is contained in the class of congestion-k depth-k minors of the class C. p. 3

Where the paper says it

Let C be a graph class of bounded expansion and denote by C • the class obtained by adding a universal vertex to every graph of C. If D is a graph class transducible from C such that D is weakly sparse, then there exists a k ∈ N such that D is contained in the class of congestion-k depth-k minors of the class C • .

This result relies on recent characterizations of weakly sparse FO transductions by Gajarsky et al. p. 0
Where the paper says it

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 [Gajarsky, Gładkowski, Jedelsk ´ y, Pilipczuk and Toru ´ nczyk, arXiv:2505.

and connects it to topological properties like fan-crossing drawings. p. 2
Where the paper says it

However, none of these properties is of much help in approaching such a basic and intriguing question as what characterizes transductions of the class of planar graphs, and more generally, of the class of graphs embeddable in a fixed surface. So far, to our knowledge, no useful direct connection (of non transducibility) to graph topological properties and graph drawings has been published.

Topological Drawing Conditions

Theorem 5 establishes the main result, stating that D is transducible from C if and only if there exists k ∈ N such that every graph of D has a monotone k-fold k-clustered fan-crossing drawing in Σ after deleting at most k of its vertices. This condition links the algebraic notion of transducibility to geometric properties related to drawings in a surface. p. 2

Where the paper says it

So far, to our knowledge, no useful direct connection (of non transducibility) to graph topological properties and graph drawings has been published. Recently, there has been notable progress in two directions which are related to our effort to understand transductions of planar and embeddable graphs: • Two groups of researchers [17, 21] independently exploited different properties related to the product structure (of planar graphs) to prove, among other results, that the class of 3D-grids is not transducible from planar graphs.

Corollary 6 provides a simpler formulation for classes of bounded maximum degree, stating that D is transducible from C if and only if there exists k′ ∈ N such that every graph of D has a k′-crossing drawing in Σ after deleting at most k′ of its edges. p. 4
Where the paper says it

Let Σ be a surface, C be the class of graphs embeddable in Σ and D be a graph class of bounded maximum degree. Then D is transducible from C, if and only if there exists k ′ ∈ N such that every graph of D has a k ′ -crossing drawing in Σ after deleting at most k ′ of its edges.

Applications to Graph Families

The results have direct applications to specific graph families, such as the class of 3D-grids. Corollary 10 concludes that the class of 3D-grids is not k-planar for any fixed k, and not k-crossing for any fixed k on any fixed surface. p. 0

Where the paper says it

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

Furthermore, Proposition 13 shows that if certain conditions hold for toroidal graphs, then every class of toroidal graphs of bounded maximum degree is transducible from the class of planar graphs and. p. 0
Where the paper says it

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

Future Research Directions

The paper suggests several avenues for future research, including conjectures about the relationship between fan-crossing drawings and strictly k-fold fan-crossing drawings and questions about the relation between different types of drawing definitions. The authors also propose a new generalization of fan-crossing drawings, called strictly k-fold fan-crossing drawings. p. 3

Where the paper says it

Equivalently, there is an assignment of every crossed edge e ′ of D′ to a fan F of D such that e ′ is an edge of the extended fan F ′ of F, and the number of fans altogether assigned to the edges of every nontrivial connected component of the crossing graph of D′ is at most ℓ. We furthermore say that a k-fold ℓ-clustered fan-crossing drawing D as above is monotone(ii) if the subdivision D′ and the assignment from the crossed edges of D′ to fans of D can be chosen to satisfy also the following condition: for every edge e = uv ∈ E(D), and denoting by P the u–v path in D′ stemming (i) This generalization somewhat resembles the k-fan-bundle-planar drawings of [1], but the core difference is that our “bundles” are allowed to branch and cross in multiple sections.

Finally, the paper points to open problems such as whether the class of toroidal graphs is transducible from planar graphs and questions about k-planar embeddings for bounded-degree toroidal graphs. p. 0
Where the paper says it

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 [Gajarsky, Gładkowski, Jedelsk ´ y, Pilipczuk and Toru ´ nczyk, arXiv:2505.

Pruning redundant reasoning tokens

The proof of Theorem 9(b) constructs a complex FO formula ξk(x, y) over the graph G. This formula is a disjunction of possibilities involving vertex colors and paths in G. p. 9

Where the paper says it

If such v comes from a crossing of two edges in D, we arbitrarily order these edges as e1, e2, and for each i ∈ {1, 2}, we give color bi to the two neighbors of v in G which belong to the former edge ei of D. The formula ξk(x, y) is constructed as a disjunction of the following possibilities: • For some 1 ≤ i ≤ m ≤ k, the vertex x contains color ci and y color c ′ i or vice versa, or • xy is an edge of the graph G, or • there exists a path P = (x, z1, .

The construction of this formula depends neither on the graph G nor on the surface Σ. p. 2
Where the paper says it

Similarly to the previous conjecture about tractability of the FO model checking problem and the aforementioned related Seese conjecture about decidability of an MSO theory, a handful of other logics sitting between the FO and MSO logic (such as so-called FO+conn logic and other) are similarly conjectured to allow efficiently solvable model checking on graph classes that do not transduce “too complex” classes (where the exact meaning of “too complex” depends on the considered logic). We hope that a better understanding of the distinction between the classes transducible from surfaceembeddable graphs and the classes non-transducible from them would allow us to find a logic between FO and MSO that corresponds to surface-embeddable graphs in the following sense: all the problems expressible in this logic can be solved on surface-embeddable graphs (and thus likely also on graph classes transducible from surface-embeddable graphs), but some of these problems become hard as soon as one considers any “reasonable” graph class non-transducible from surface-embeddable graphs.

Where the gains come from

The core of Theorem 9(b) involves constructing a drawing D3 which is an embedding in Σ. This drawing D3 is obtained by contracting components of the crossing graph into vertices and then subdividing rays. p. 3

Where the paper says it

Definition 4. A drawing D of a graph G in a surface Σ is called k-fold ℓ-clustered fan-crossing if there is a drawing D′ obtained from D by subdividing each edge with at most k − 1 new vertices, such that every connected component of the crossing graph of D′ is a subset of the union of the edge sets of at most ℓ extended fans of D′ .

The resulting drawing D3 is shown to be an O(k)-fold O(k)-clustered fan-crossing drawing of H, which is also trivially monotone. p. 4
Where the paper says it

Then D is transducible from C, if and only if there exists k ∈ N such that every graph of D has a monotone k-fold k-clustered fan-crossing drawing in Σ after deleting at most k of its vertices. Note that any k-fold k-clustered fan-crossing drawing of a graph G ∈ D is trivially a (∆(G) · k 2 )- crossing drawing in the same surface, and that deleting some k vertices from G is in this context equivalent to deleting the at most ∆(G) · k edges incident to them.

How the training signal is built

The forward direction of Theorem 5 uses Theorem 3 and Theorem 8 to show that if D is transducible from C, then every graph in D has the required drawing. The proof involves constructing a planar graph H1 and using minor models to establish the necessary structural properties. p. 6

Where the paper says it

If c = 1, we speak simply about a depth-d minor of G. When discussing congestion-c depth-d minor models α of planar graphs and graphs of surfaces, it is often convenient to assume that that no two vertices of H are mapped to the same set of A.

The forward direction of Theorem 6 follows easily as mentioned in Section 1. The proof of the ‘⇒’ of Theorem 6 is straightforward. p. 7

Where the paper says it

Jedelsk ´ y´ Fig. 3: An illustration of the proof of Theorem 8.

The converse ‘⇐’ directions of both Theorem 5 and Theorem 6 are stated in the next Theorem 9. Part (a) of Theorem 9 is easier to prove than part (b). p. 8

Where the paper says it

The converse ‘⇐’ directions of both Theorem 5 and Theorem 6 are stated (as parts (b) and (a), respectively) in the next Theorem 9. Although part (a) of Theorem 9 is actually implied by part (b), we prefer to prove the parts separately since (a) is much easier and it accessibly illustrates the necessary concepts.

The construction of the FO formula ξk(x, y) depends neither on the graph G nor on the surface Σ. p. 9
Where the paper says it

The said properties are routinely expressible in FO logic, giving the desired FO formula ξk(x, y) over G. Note that ξk depends on the parameter k in two ways; in the first point where a disjunction of m ≤ k possibilities for color pairs ci and c ′ i occurs, and in the third point in which we use a separate existential

The proof of Theorem 9(a) involves turning crossings into new vertices and subdividing edges to create a graph G''. The coloring scheme introduced in G is routine, and the resulting FO formula ξk(x, y) captures precisely the edges of H. p. 9

Where the paper says it

We now color the vertices of G by sets of colors (which can easily be transformed into singleton colors at the end), as follows. For simplicity let us say that we give a color to a vertex v, which means that the resulting color of v will be the collection of all colors given to v throughout the construction of coloring.

The proof of Theorem 9(b) involves a detailed construction of colors for vertices in G. This coloring scheme is intricate, and the final formula ξk(x, y) depends neither on the graph G nor on the surface Σ. p. 9

Where the paper says it

The said properties are routinely expressible in FO logic, giving the desired FO formula ξk(x, y) over G. Note that ξk depends on the parameter k in two ways; in the first point where a disjunction of m ≤ k possibilities for color pairs ci and c ′ i occurs, and in the third point in which we use a separate existential

The forward direction of Theorem 9(b) concludes by showing that if xy is uncrossed in D, then G = ξk(x, y) if and only if xy ∈ E(H)∩E(D2). This establishes the equivalence needed for the proof. p. 5

Where the paper says it

Hlinenˇ y and J. Jedelsk ´ y´ 2 Interpretations, Transductions, and Congested Shallow Minors We consider only finite simple graphs (forbidding parallel edges is natural and necessary when dealing with FO transductions since we view edges as symmetric binary relation; and loops can be simulated using colors if needed).

The final part of Theorem 9(b) proves that if xy is not an edge in H, then G!= ξk(x, y). p. 9

Where the paper says it

a) a k-crossing drawing in Σ, or b) a monotone k-fold k-clustered fan-crossing drawing in Σ. Then there is an FO formula ξk(x, y) depending only on k, and a colored graph G on vertex set V (G) ⊇ V (H) embedded in Σ such that H equals ξk(G)[V (H)] (the subgraph of ξk(G) induced on V (H)).

This relies on proving z4q ∈ V (F¯x) ∩ V (F¯y), which implies xy ∈ E(H), a contradiction. p. 0
Where the paper says it

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.

The proof of Theorem 9(a) shows that the construction of ξk depends on k in two ways, and in the third point in which we use a separate existential quantifier for every internal vertex of the path P. This dependence on k is what allows the formula to capture precisely the necessary properties. p. 9

Where the paper says it

, zp, y) in G of length at most 3(k + 1), such that for every 1 < i < p the vertex zi contains color b1 or b2, or zi contains color b0 and the color sets of its neighbors zi−1 and zi+1 both contain the same color among b1 or b2. The said properties are routinely expressible in FO logic, giving the desired FO formula ξk(x, y) over G.

p. 9
Where the paper says it

, zp, y) in G of length at most 3(k + 1), such that for every 1 < i < p the vertex zi contains color b1 or b2, or zi contains color b0 and the color sets of its neighbors zi−1 and zi+1 both contain the same color among b1 or b2. The said properties are routinely expressible in FO logic, giving the desired FO formula ξk(x, y) over G.

The proof of Theorem 9(b) shows that the walk Pxy is accepted by the third point in the definition of ξk. This acceptance is guaranteed by our coloring of G and the way it is checked by ξk. p. 0

Where the paper says it

2026, 30th June 2026; accepted 4thAug. We introduce, for every surface Σ, a two-way connection between definability of a graph class 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 C in Σ.

The proof of Theorem 9(b) concludes that G = ξk(x, y), as needed. This completes the proof of Theorem 9(b). p. 7

Where the paper says it

Jedelsk ´ y´ Fig. 3: An illustration of the proof of Theorem 8.

p. 7
Where the paper says it

Jedelsk ´ y´ Fig. 3: An illustration of the proof of Theorem 8.

The proof of the ‘⇒’ of Theorem 6 follows easily as mentioned in Section 1. The proof of ‘⇒’ of Theorem 6 is straightforward. p. 7

Where the paper says it

Jedelsk ´ y´ Fig. 3: An illustration of the proof of Theorem 8.

The forward direction of Theorem 9(b) concludes by showing that if a graph class D satisfies the assumptions of Theorem 6 (resp., of Theorem 5) for some k and some surface Σ, then every graph H ∈ D satisfies the conditions of Theorem 9 a) (resp. p. 8

Where the paper says it

Finally, since multiple intersections between pairs of arcs are allowed, this drawing satisfies all desired properties. Secondly, as H is a subgraph of the intersection graph of R, for every edge f = vw ∈ E(H) we have a simple arc αf ⊆ ϱv ∪ ϱw between the roots of ϱv and ϱw.

, of Theorem 9 b)) for the same k and Σ. p. 1
Where the paper says it

Jedelsk ´ y´ Fig. 1: Illustration depicting how the transduction of Theorem 1 creates C5 from subdivided K5.

This establishes an FO transduction of the class of all graphs embeddable in Σ that contains all graphs of D. p. 0
Where the paper says it

2026, 30th June 2026; accepted 4thAug. We introduce, for every surface Σ, a two-way connection between definability of a graph class 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 C in Σ.

The proof of Theorem 9(a) shows that the construction of ξk depends on k in two ways, and in the third point in which we use a separate existential quantifier for every internal vertex of the path P. This dependence on k is what allows the formula to capture precisely the necessary properties.

The proof of Theorem 9(b) shows that G = ξk(x, y), as needed. This completes the proof of Theorem 9(b).

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Automated proof of non-transducibility results from drawing properties: The system can derive non-transducibility results by showing that a class is not k-planar for any fixed k, based on the nonexistence of fan-crossing drawings in a given surface, or vice versa.

  2. Characterization of transducibility via topological constraints: The system can determine if a graph class D is transducible from a surface embeddable class C by checking if every graph in D has a monotone k-fold k-clustered fan-crossing drawing in the surface Σ after deleting at most k vertices.

  3. Efficient identification of structural properties for model checking: The system can leverage the connection between non-transducibility and nonexistence of drawings to infer that certain problems are hard, linking the lack of transduction to the complexity of first-order model checking problems on graph classes.

  4. Verification of bounded maximum degree properties: For a class D where graphs have bounded maximum degree, the system can verify transducibility by checking if every graph in D has a k-crossing drawing after deleting at most k edges, using Corollary 6.

  5. Application to specific graph classes: The system can conclude that the class of 3D-grids is not k-planar for any fixed k and not k-crossing for any fixed k on any fixed surface, as stated in Corollary 10, based on Theorem 6 and the maximum degree of 3D-grids.

  6. Solving specific open problems in graph theory: The system can provide a framework to investigate Problem 11 (toroidal graphs transducibility) and Problem 12 (k-planarity for bounded degree toroidal graphs) by linking them to the existence of specific fan-crossing drawings or k-planar drawings.

  7. Deriving structural bounds for graph classes: The system can use Theorem 3 to show that if a graph class D is transducible from a class C of bounded expansion, then D is contained in the class of congestion-k depth-k minors of C for some fixed k.

Abstract

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

Sources

Related papers