k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs
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 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). 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.Where the paper says it
Where the paper says it
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 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+). 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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
•
. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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). 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).Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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, . 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 paper says it
Where the paper says it
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 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′
. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
The forward direction of Theorem 6 follows easily as mentioned in Section 1. The proof of the ‘⇒’ of Theorem 6 is straightforward. p. 7 Jedelsk ´ y´
Fig. 3: An illustration of the proof of Theorem 8.Where the paper says it
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 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 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 existentialWhere the paper says it
Where the paper says it
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 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.Where the paper says it
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 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 existentialWhere the paper says it
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 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).Where the paper says it
The final part of Theorem 9(b) proves that if xy is not an edge in H, then G!= ξk(x, y). p. 9 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)). 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.Where the paper says it
Where the paper says it
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 , 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. , 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.Where the paper says it
Where the paper says it
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 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 Σ.Where the paper says it
The proof of Theorem 9(b) concludes that G = ξk(x, y), as needed. This completes the proof of Theorem 9(b). p. 7 Jedelsk ´ y´
Fig. 3: An illustration of the proof of Theorem 8. Jedelsk ´ y´
Fig. 3: An illustration of the proof of Theorem 8.Where the paper says it
Where the paper says it
The proof of the ‘⇒’ of Theorem 6 follows easily as mentioned in Section 1. The proof of ‘⇒’ of Theorem 6 is straightforward. p. 7 Jedelsk ´ y´
Fig. 3: An illustration of the proof of Theorem 8.Where the paper says it
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 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. Jedelsk ´ y´
Fig. 1: Illustration depicting how the transduction of Theorem 1 creates C5 from subdivided K5. 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 Σ.Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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
- First-order transducibility among classes of sparse graphs
- Efficient reversal of transductions of sparse graph classes
- Product structure of graph classes with strongly sublinear separators
- Structure of $k$-Matching-Planar Graphs
- Graph classes through the lens of logic
Related papers
- The Rhythm of the Tiles: Narrow and Low Temperature Computation and Simulation in Synchronous Tile Self-Assembly
- Covering Points with Rectangular Boundaries
- Tiling 3D Space by (Translates of) a Single Polycube is Undecidable
- Quadratic Complexity of Voronoi Diagrams in R cubed for Lines in a Single Ruling of a Regulus
- Minimum central circles: chain order, seam obstructions, and exact finite certification
- One Shot, Twenty-One Balls: A Computer-Assisted Proof of a Single-Stroke Total Clearance in an Idealized Model of Snooker