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

summary

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…

In short

The paper connects whether one graph class can be transformed into another (transducibility) using first-order logic to geometric properties of drawings, specifically fan-crossing drawings. It establishes that transducibility is equivalent to certain drawing conditions, allowing researchers to prove non-transducibility by showing the absence of these specific topological structures.

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 used across episodes

This episode discusses

The paper

k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs · Read on arXiv

Petr Hlinenď y, Jan Jedelskľ y

Masaryk University

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

DOI: 10.46298/dmtcs.17710

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.

More episodes

← Home