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

Jan Jedelsk\'y; Petr Hlin\v{e}n\'y

REVIEW 3 major objections 5 minor 23 references

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

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A weakly sparse graph class is first-order transducible from the graphs embeddable in a fixed surface precisely when, for some fixed k, every graph in it has a monotone k-fold k-clustered fan-crossing drawing on that surface after…

desk verdict New equivalence between transducibility and fan-crossing drawings, with the forward direction leaning on a plausible but unproved recent theorem; worth refereeing but ask for a proof sketch of that dependency. read the letter →

arxiv 2506.08585 v4 pith:EK26MMGX submitted 2025-06-10 cs.CG cs.LOmath.CO

Petr Hliněný , Jan Jedelský This is my paper

classification cs.CGcs.LOmath.CO MSC 05C1005C6203C1368R10

keywords planargraphssurfaceembeddingsk-planardrawingsfan-crossingfirst-ordertransductionsboundedexpansionweaklysparsegraphclassestoroidal

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

First-order transductions are logical recipes that turn one graph class into another, and the paper asks which sparse target classes can be obtained this way from the graphs embeddable in a fixed surface. The answer it proposes is a purely geometric one: a weakly sparse class qualifies exactly when, for some fixed k, every graph in it can be drawn on that surface as a monotone k-fold k-clustered fan-crossing drawing after deleting at most k vertices. For bounded-degree targets, the condition simplifies to having a bounded number of crossings per edge, i.e., k-planarity in the plane. This two-way bridge turns logical non-definability proofs into drawing impossibility proofs and back, which the paper exploits to reprove that 3D-grids are not transducible from planar graphs and to give a concrete target for the open question of whether toroidal graphs are transducible from planar graphs.

What carries the argument

One central object is the monotone k-fold k-clustered fan-crossing drawing: a drawing in which each edge may be subdivided by at most k−1 new vertices so that every connected component of the resulting crossing graph is covered by at most k extended fans (sets of subdivided edges all incident to one center vertex), with the monotonicity condition that along each original edge the fan assignment changes at most once, from the fan of one endpoint to the fan of the other. The companion machinery is the congested shallow minor: a minor model whose model sets have radius at most k and in which each host vertex belongs to at most k model sets. The proof that logical transductions imply such drawings (the forward direction) composes the black-box Theorem 1 — which places every weakly sparse transducible class inside bounded-congestion bounded-depth minors of the source class with a universal vertex added — with a lemma that converts any such minor model into the required fan-crossing drawing. The reverse direction constructs, for each fixed k, a first-order formula ξ_k and a colored surface embedding that recovers the original graph on the vertex set of the drawing, so that the drawing literally becomes the logical interpretation.

What would settle it

Find a weakly sparse graph class D that is FO-transducible from the planar graphs but provably is not contained, for any fixed k, in the class of congestion-k depth-k minors of planar graphs with a universal vertex added; that would refute the black-box theorem and hence the forward direction of the main characterization. One concrete route: show a bounded-degree class transducible from planar graphs whose members force more than k crossings on some edge in every planar drawing, even after deleting any k vertices or edges — a violation of Corollary 4 that would be directly observable from a drawing lower-bound proof.

Watch

Extended reading notes

Core claim

The paper claims Theorem 3 as its central discovery: for any surface Σ, with C the class of graphs embeddable in Σ, a weakly sparse class D is FO-transducible from C if and only if for some fixed k every graph of D has a monotone k-fold k-clustered fan-crossing drawing in Σ after deleting at most k of its vertices. When D also has bounded maximum degree, this collapses to the simpler statement that D is transducible from C iff for some fixed k every graph of D has a k-crossing drawing in Σ after deleting at most k of its edges (Corollary 4). The authors prove the drawing-to-logic direction completely, by constructing a single first-order formula ξ_k plus a colored surface embedding that recovers each graph of D as an induced subgraph; the logic-to-drawing direction runs through the congested-minor characterization of transductions of bounded-expansion classes together with a lemma that turns any such minor model into the required fan-crossing drawing.

Load-bearing premise

The forward half of the characterization depends on an unproved black-box theorem from a related preprint, namely that every weakly sparse class transducible from a bounded-expansion class sits inside its bounded-congestion, bounded-depth minors after adding a universal vertex; if that theorem carries hidden hypotheses or is wrong, the 'only if' direction fails even though the reverse direction is proved from scratch in this paper.

Editorial extensions

If this is right

The 3D-grid class is not k-planar for any fixed k, and more generally not k-crossing on any fixed surface (Corollary 9), so no fixed crossing budget can draw 3D grids on any surface.
Since 3D-grids fail the drawing condition, they are not FO-transducible from planar graphs, giving a third independent route to a result previously obtained by two other groups.
If there is any d ≥ 3 and ℓ for which every toroidal graph of maximum degree d is ℓ-planar after deleting at most ℓ edges, then every bounded-degree toroidal class is transducible from planar graphs (Proposition 12).
An affirmative answer to whether toroidal graphs are transducible from planar would force every toroidal graph to admit a monotone k-fold k-clustered fan-crossing drawing for some fixed k, which the authors consider unlikely and propose as a concrete attack on the problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One extension not pursued in the paper: the bridge suggests a research program in which non-transducibility is shown by proving lower bounds on crossings per edge or on fan-cluster complexity, a concrete geometric task rather than a model-theoretic one.
The drawing-to-logic direction (Lemma 8) is unconditional: even if the black-box theorem on congested minors were to fail, any class admitting these bounded drawings for fixed k would still be weakly sparse transducible from the surface-embeddable graphs, so half of the characterization stands alone.
If the authors' closing conjecture is true — that every classical fan-crossing drawing is k-fold ℓ-clustered for small k and ℓ — then Theorem 3 would automatically extend to the classical fan-crossing setting, making the characterization much easier to apply.
For bounded-degree classes, Corollary 4 turns a logic question into a crossing-number question with a deletion-tolerance parameter; one could try to certify non-transducibility computationally for candidate classes by showing the minimal number of crossings per edge grows unboundedly even after deleting k edges.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take on arXiv:2506.08585. The genuinely new thing is the drawing class they define and the two-way characterization in Theorem 3: for a surface Σ, a weakly sparse class D is transducible from Σ-embeddable graphs iff every graph in D has a monotone k-fold k-clustered fan-crossing drawing in Σ after deleting k vertices. That's a real bridge between logic and graph drawing, and it gives a clean new angle on the toroidal-graphs question. The reverse direction (Lemma 8) is self-contained and carefully proved, including the FO formula. Lemma 7's construction is explicit and plausible.

The main soft spot is the forward direction. It uses Theorem 1 from the Gajarský et al. preprint (arXiv:2505.15655) as a black box, and that paper has overlapping authorship and is not yet peer-reviewed. That dependency is genuine, but note the stress-test worry that C• is not bounded expansion does not land: Theorem 1 is applied to C (the surface-embeddable class, which is bounded expansion), and its conclusion is about C•. So that specific red flag is a false lead. The real issue is simply that the central iff inherits the correctness of a nontrivial external theorem. If that theorem is wrong, the forward direction fails; the reverse still stands. I'd want the referee to verify Theorem 1's proof or at least see a detailed sketch in an appendix.

A second, minor issue: Lemma 7 says the constructed drawing is 'trivially monotone' and gives only a sentence. The monotone condition is subtle, and the proof would be more convincing with a few lines explaining the switch point along each edge. Also, the footnote about the conference version omitting 'monotone' is an honest disclosure, but it means the definition has been refined; the current version uses it consistently.

The 3D-grids corollary is known, but the authors openly say it is an illustration; the real meat is the equivalence itself.

Bottom line: this is a serious paper, the math is mostly explicit and the main theorem is a genuine new contribution. I'd send it to referees. I'd ask them to check the dependency on Theorem 1 and to ask the authors to expand the monotone argument. Despite the external dependency, I think it deserves review rather than a desk reject.

Referee Report

3 major / 5 minor

Summary. The paper introduces k-fold ℓ-clustered fan-crossing drawings in surfaces and proves Theorem 3: for a surface Σ, a weakly sparse graph class D is transducible from the class of graphs embeddable in Σ if and only if every H in D has a monotone k-fold k-clustered fan-crossing drawing in Σ after deleting at most k vertices. The forward direction combines Theorem 1 of Gajarský et al. (arXiv:2505.15655) with a minor-to-drawing lemma (Lemma 7). The reverse direction is proved constructively in Lemma 8 by encoding the drawing into an FO formula and an embedded colored graph. Corollary 4 gives a bounded-degree version with k-crossing drawings, and applications to 3D grids and toroidal graphs are discussed.

Significance. If Theorem 3 is correct, it is a significant bridge between FO transductions and graph drawing, giving a concrete topological obstruction for weak transducibility from surface-embeddable sources. The self-contained reverse direction with explicit FO formulas is a substantial contribution, and the 3D-grid non-k-planarity application is elegant. The main caveat is that the forward direction is not self-contained: it inherits an unproved, recent, overlapping-author characterization. The paper is transparent about this dependence, which makes the conditional value clear.

major comments (3)

[Section 3, proof of '⇒' of Theorem 3] The only-if direction is exactly Theorem 1 of [13] followed by Lemma 7. Theorem 1 is a recent preprint with overlapping authorship and is neither proved nor sketched here. Because the characterization in Theorem 3 is an iff, the only-if direction collapses if Theorem 1 is false or has hypotheses not met. I request that the authors either include a proof or detailed proof sketch of the quoted theorem, or state the main theorem as conditional on [13] being accepted. In particular, verify explicitly that the theorem's hypotheses (C bounded expansion, D weakly sparse and transducible from C) are sufficient for the pointwise conclusion that D is contained in the congestion-k depth-k minors of C•, and that no extra assumptions on D such as heredity or closure under disjoint unions are used. The fact that C• is not itself bounded expansion makes this check non-vacuous.
[Section 3, Lemma 7] The proof concludes that the constructed O(k)-fold O(k)-clustered fan-crossing drawing is 'trivially monotone by our construction,' but the monotone condition in Definition 2 is load-bearing for Theorem 3, and the footnote notes that a previous version omitted it. Please provide the missing verification: for each edge f=vw, after placing a subdivision vertex at the meeting point b_f, every crossed edge on the v-side of b_f is assigned to the fan centered at v and every crossed edge on the w-side to the fan centered at w.
[Section 3, Lemma 8(b), case (ii)] In the induction proving that an accepted path forces xy∈E(H), the step 'let j be such that F^i_j = F_x' needs justification. The formula's color condition only guarantees existence of some fan index j at component m_i; one must argue that the fan whose R/T side contains z_{4q} on the x-side of the component is exactly the fan centered at x. Please expand this step to make the induction sound.

minor comments (5)

[Section 3, Lemma 8(b), case (i)] The bound 'at most k of the vertices m_i lie on P_xy' is justified by the k-fold subdivision of the original edge (at most k subsegments that carry crossings), not by the k-clustered condition as stated. Please correct the reason given.
[Section 3, Lemma 8(a)] There is a typo 'ξ+k(x,y)' in the verification paragraph; it should be 'ξ_k(x,y)'.
[Section 4, Proposition 12] The assumption allows deleting at most ℓ edges, but the proof moves directly to an induced subgraph G'_1 obtained by deleting ≤ℓ vertices. This is fixable since G1 has maximum degree 3, but the short argument should be included.
[Section 1, abstract] The notation 'C' is used both for the source class of embeddable graphs and for the target class in the sentence 'If the considered class C is additionally of bounded maximum degree'; please clarify the notation.
[Section 3, Lemma 7] The phrase 'for some k'∈O(k)' should be reconciled with the integer quantifier in Theorem 3; since k is arbitrary this is fine, but the statement could explicitly say that k may be increased to absorb constants.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the drawing/transduction equivalence is established by explicit constructions in Lemmas 7 and 8, and the only external dependency (Theorem 1 of [13]) is an overlapping-author characterization used as a black box, which is a correctness risk rather than a logical circle.

full rationale

The claimed iff in Theorem 3 is not assumed as an input. The reverse direction is self-contained: Lemma 8(b) takes a monotone k-fold k-clustered fan-crossing drawing and constructs a fixed FO formula xi_k plus an embedded colored graph G, verifying exactly that G |= xi_k(x,y) iff xy in E(H). Lemma 7 is also proved in detail, converting a congestion-k depth-k minor model into such a drawing. The forward direction is the only part that leans on an external result: the proof says 'By Theorem 1, there is G in C^bullet...' and 'The forward direction of Theorem 3 is now finished from Theorem 1 and Lemma 7.' Theorem 1 is quoted from arXiv:2505.15655, a recent preprint whose author list includes the current second author. This is a load-bearing dependency on a theorem not proved in the present paper, and if that theorem had hidden hypotheses the main iff would collapse. However, it is not circularity: Theorem 1 is a different statement about transducible weakly sparse classes from bounded-expansion classes, it is not defined in terms of Theorem 3, and no parameter is fitted to force the conclusion. The footnote admitting that the conference version omitted 'monotone' is a correction of a prior gap, not a circular step. Hence no circular step; the self-citation is a verifiability/correctness caveat rather than a logical circle.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted; this is a pure mathematics paper. The central equivalence inherits its forward direction from Theorem 1 of Gajarský et al. [13], a recent external characterization by an overlapping author set. It also assumes standard facts about surface embeddings and sparsity. The new drawing class is a mathematical definition, not an empirical entity, so no invented physical entities are introduced.

assumptions (4)

domain assumption Theorem 1 of Gajarský et al. [13]: if C is a bounded-expansion class and D is weakly sparse and transducible from C, then D is contained in the class of congestion-k depth-k minors of C^•.
Used as a black box in the proof of the forward direction of Theorem 3 (Section 3, Proof of => of Theorem 3). The theorem is from a recent preprint with overlapping authorship and is not proved or formalized in this paper.
domain assumption Surface-embeddable graph classes are weakly sparse and have bounded expansion.
Stated in Section 2, citing [20, Section 5.5]. Needed to apply Theorem 1 to the class C of graphs embeddable in a fixed surface.
domain assumption Transductions on surface-embeddable classes can be taken non-copying, because copying can be simulated by adding leaves and colors.
Stated in Section 2 in the paragraph on transductions. It simplifies the definition but is a nontrivial background fact about FO transductions.
standard math Contractions of non-loop edges preserve embeddability in a surface; standard drawing perturbation facts hold.
Used in Lemma 8(b) to contract crossing-graph components into stars while keeping the drawing an embedding, and to remove tangential intersections.

how reviews work

0 comments

Cite this review

Pith. "Pith review of k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs." pith.science (2026). https://pith.science/paper/EK26MMGX

@misc{pith2026250608585,
  author       = {Pith},
  title        = {Pith review of: k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EK26MMGX}},
  note         = {Machine review of arXiv:2506.08585}
}

abstract

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 embeddable in $\Sigma$ and a certain variant of fan-crossing drawings of the graphs from $\mathcal C$ in $\Sigma$. If the considered class $\mathcal C$ is additionally of bounded maximum degree, then the restriction on drawings of the graphs from $\mathcal C$ in $\Sigma$ is simply to have a bounded number of crossings per edge (such as being $k$-planar for fixed~$k$ if $\Sigma$ 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 derive 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\'y, G{\l}adkowski, Jedelsk\'y, Pilipczuk and Toru\'nczyk, arXiv:2505.15655].

Figures

Figures reproduced from arXiv: 2506.08585 by the authors.

**Figure 1.** (a) An example of a monotone 2-fold 2-clustered fan-crossing drawing D. The four subdivision vertices (i.e., the set V (D ′ ) \ V (D) from Definition 2) are hollow, and the three components of the crossing graph of the subdivided drawing D ′ are emphasized by shade colors red, green and blue. (b) An ordinary fan-crossing drawing of a large m-vertex graph which is not 1-fold ℓ-clustered for any ℓ < m 2 , because no s… view at source ↗

**Figure 2.** An illustration of the proof of Lemma 7. The five blue bags (dashed lines in the picture) show the five model sets of a congestion-2 depth-2 minor model of a 5-vertex graph H in the depicted graph G (which is a 3 × 5 square grid pictured in black). The chosen small disks δu and δe at the vertices and edges of G are shaded gray. The set R of branching arcs representing the vertices of H (so, one per each blue bag) is… view at source ↗

**Figure 3.** An illustration of the proof of Lemma 8(a) (here with X = ∅); turning a 2-planar drawing D into a planar colored drawing D ′′. Color b0 is red, and b1 and b2 are green and blue. H := H′ − U is a congestion-k depth-k minor of the graph G − u which is embeddable in Σ, and we conclude with the drawing and bound k ′ by Lemma 7. The converse ‘⇐’ directions of both Theorem 3 and Corollary 4 are together stated in the next… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: An illustration of the proof of Lemma 8(b) (here with X = ∅). (left) Component Mi of the crossing graph of the drawing D1 from the proof, with sets F 1 i , F 2 i , F 3 i of paths subdividing original fans centered at w 1 i , w 2 i , w 3 i . (right) The corresponding fr…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 8 canonical work pages

[13]

First-order transducibility among classes of sparse graphs

J. Gajarsk ´y, J. Gładkowski, J. Jedelsk´y, M. Pilipczuk, and S. Toru´nczyk. First-order transducibility among classes of sparse graphs.CoRR, abs/2505.15655, 2025. doi: 10.48550/ARXIV .2505.15655

work page Pith review arXiv doi:10.48550/arxiv.2505.15655 2025
[1]

Angelini, M

P. Angelini, M. A. Bekos, M. Kaufmann, P. Kindermann, and T. Schneck. 1-fan-bundle-planar drawings of graphs.Theor. Comput. Sci., 723:23–50, 2018. doi: 10.1016/J.TCS.2018.03.005

doi:10.1016/j.tcs.2018.03.005 2018
[2]

Bonnet, E

´E. Bonnet, E. J. Kim, S. Thomass ´e, and R. Watrigant. Twin-width I: tractable FO model checking. J. ACM, 69(1):3:1–3:46, 2022. doi: 10.1145/3486655. URLhttps://doi.org/10.1145/ 3486655

doi:10.1145/3486655 2022
[3]

On first-order transductions of classes of graphs

S. Braunfeld, J. Ne ˇsetˇril, P. Ossona de Mendez, and S. Siebertz. On first-order transductions of classes of graphs.CoRR, abs/2208.14412, 2022. doi: 10.48550/ARXIV .2208.14412

work page Pith review arXiv doi:10.48550/arxiv.2208.14412 2022
[4]

Courcelle, J

B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width.Theory Comput. Syst., 33(2):125–150, 2000. doi: 10.1007/ S002249910009

work page
[5]

J. Dreier. Lacon-, shrub- and parity-decompositions: Characterizing transductions of bounded ex- pansion classes.Log. Methods Comput. Sci., 19(2), 2023. doi: 10.46298/LMCS-19(2:14)2023. URLhttps://doi.org/10.46298/lmcs-19(2:14)2023

doi:10.46298/lmcs-19(2:14)2023 2023
[6]

Dreier, N

J. Dreier, N. M ¨ahlmann, and S. Siebertz. First-order model checking on structurally sparse graph classes. In B. Saha and R. A. Servedio, editors,Proceedings of the 55th Annual ACM Sympo- sium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 567–580. 14P . Hlin ˇen´y and J. Jedelsk´y ACM, 2023. doi: 10.1145/3564246.3585186. UR...

arXiv 2023
[7]

Dreier, N

J. Dreier, N. M ¨ahlmann, and S. Toru ´nczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In B. Mohar, I. Shinkar, and R. O’Donnell, editors,Pro- ceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1550–1560. ACM, 2024. doi: 10.1145/3618260.36...

arXiv 2024

Show all 23 references

[8]

Dreier, J

J. Dreier, J. Gajarsk ´y, and M. Pilipczuk. Efficient reversal of transductions of sparse graph classes. CoRR, abs/2601.14906, 2026. doi: 10.48550/ARXIV .2601.14906. URLhttps://doi.org/ 10.48550/arXiv.2601.14906

2026 doi
[9]

Dujmovic, D

V . Dujmovic, D. Eppstein, and D. R. Wood. Structure of graphs with locally restricted crossings. SIAM J. Discret. Math., 31(2):805–824, 2017. doi: 10.1137/16M1062879

2017 doi
[10]

Dvo ˇr´ak and D

Z. Dvo ˇr´ak and D. R. Wood. Product structure of graph classes with strongly sublinear separators. CoRR, abs/2208.10074, 2022. doi: 10.48550/ARXIV .2208.10074

2022 doi arXiv
[11]

Gajarsk ´y, P

J. Gajarsk ´y, P. Hlinˇen´y, J. Obdrˇz´alek, D. Lokshtanov, and M. S. Ramanujan. A new perspective on FO model checking of dense graph classes.ACM Trans. Comput. Log., 21(4):28:1–28:23, 2020. doi: 10.1145/3383206. URLhttps://doi.org/10.1145/3383206

2020 doi
[12]

Gajarsk ´y, S

J. Gajarsk ´y, S. Kreutzer, J. Nesetril, P. O. de Mendez, M. Pilipczuk, S. Siebertz, and S. Torunczyk. First-order interpretations of bounded expansion classes.ACM Trans. Comput. Log., 21(4):29:1– 29:41, 2020. doi: 10.1145/3382093. URLhttps://doi.org/10.1145/3382093

2020 doi
[15]

Ganian, P

R. Ganian, P. Hlinen ´y, J. Nesetril, J. Obdrz ´alek, P. O. de Mendez, and R. Ramadurai. When trees grow low: Shrubs and fast MSO1. In B. Rovan, V . Sassone, and P. Widmayer, editors,Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, B...

2012 doi
[16]

Ganian, P

R. Ganian, P. Hlin ˇen´y, J. Neˇsetˇril, J. Obdrˇz´alek, and P. Ossona de Mendez. Shrub-depth: Capturing height of dense graphs.Log. Methods Comput. Sci., 15(1), 2019. doi: 10.23638/LMCS-15(1:7)2019. URLhttps://doi.org/10.23638/LMCS-15(1:7)2019

2019 doi
[17]

Hendrey, N

K. Hendrey, N. Karol, and D. R. Wood. Structure ofk-matching-planar graphs.CoRR, abs/2507.22395, 2025. doi: 10.48550/ARXIV .2507.22395. URLhttps://doi.org/10. 48550/arXiv.2507.22395. k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs15

2025 doi
[18]

Hlin ˇen´y and J

P. Hlin ˇen´y and J. Jedelsk ´y. Transductions of graph classes admitting product structure. In40th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2025, Singapore, June 23-26, 2025, pages 843–855. IEEE, 2025. doi: 10.1109/LICS65433.2025.00069. URLhttps://doi. org...

2025
[19]

Hlin ˇen´y and J

P. Hlin ˇen´y and J. Jedelsk´y. k-planar and fan-crossing drawings and transductions of planar graphs. In SOFSEM 2026, Proceedings, volume 16448 ofLecture Notes in Computer Science, pages 505–516. Springer, 2026

2026
[20]

Ne ˇsetˇril and P

J. Ne ˇsetˇril and P. O. de Mendez.Sparsity - Graphs, Structures, and Algorithms, volume 28 ofAlgorithms and combinatorics. Springer, 2012. ISBN 978-3-642-27874-7. doi: 10.1007/ 978-3-642-27875-4. URLhttps://doi.org/10.1007/978-3-642-27875-4

2012 doi
[21]

Ne ˇsetˇril, P

J. Ne ˇsetˇril, P. Ossona de Mendez, M. Pilipczuk, R. Rabinovich, and S. Siebertz. Rankwidth meets stability. In D. Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algo- rithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2014–2033. SIAM, 20...

2021 doi
[22]

Pilipczuk

M. Pilipczuk. Graph classes through the lens of logic.CoRR, abs/2501.04166, 2025. doi: 10.48550/ ARXIV .2501.04166

2025 doi arXiv
[23]

S. Shelah. Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory.Annals of Mathematical Logic, 3(3), 1971. doi: 10.1016/0003-4843(71)90015-5. URLhttps://doi.org/10.1016/0003-4843(71)90015-5

1971 doi
[24]

Toru ´nczyk

S. Toru ´nczyk. Flip-width: Cops and robber on dense graphs. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 663–700. IEEE, 2023. doi: 10.1109/FOCS57990.2023.00045. URLhttps://doi.org/10. 1109/FOCS57990...

2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [13]

First-order transducibility among classes of sparse graphs

J. Gajarsk ´y, J. Gładkowski, J. Jedelsk´y, M. Pilipczuk, and S. Toru´nczyk. First-order transducibility among classes of sparse graphs.CoRR, abs/2505.15655, 2025. doi: 10.48550/ARXIV .2505.15655

work page Pith review arXiv doi:10.48550/arxiv.2505.15655 2025

[2] [1]

Angelini, M

P. Angelini, M. A. Bekos, M. Kaufmann, P. Kindermann, and T. Schneck. 1-fan-bundle-planar drawings of graphs.Theor. Comput. Sci., 723:23–50, 2018. doi: 10.1016/J.TCS.2018.03.005

doi:10.1016/j.tcs.2018.03.005 2018

[3] [2]

Bonnet, E

´E. Bonnet, E. J. Kim, S. Thomass ´e, and R. Watrigant. Twin-width I: tractable FO model checking. J. ACM, 69(1):3:1–3:46, 2022. doi: 10.1145/3486655. URLhttps://doi.org/10.1145/ 3486655

doi:10.1145/3486655 2022

[4] [3]

On first-order transductions of classes of graphs

S. Braunfeld, J. Ne ˇsetˇril, P. Ossona de Mendez, and S. Siebertz. On first-order transductions of classes of graphs.CoRR, abs/2208.14412, 2022. doi: 10.48550/ARXIV .2208.14412

work page Pith review arXiv doi:10.48550/arxiv.2208.14412 2022

[5] [4]

Courcelle, J

B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width.Theory Comput. Syst., 33(2):125–150, 2000. doi: 10.1007/ S002249910009

work page

[6] [5]

J. Dreier. Lacon-, shrub- and parity-decompositions: Characterizing transductions of bounded ex- pansion classes.Log. Methods Comput. Sci., 19(2), 2023. doi: 10.46298/LMCS-19(2:14)2023. URLhttps://doi.org/10.46298/lmcs-19(2:14)2023

doi:10.46298/lmcs-19(2:14)2023 2023

[7] [6]

Dreier, N

J. Dreier, N. M ¨ahlmann, and S. Siebertz. First-order model checking on structurally sparse graph classes. In B. Saha and R. A. Servedio, editors,Proceedings of the 55th Annual ACM Sympo- sium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 567–580. 14P . Hlin ˇen´y and J. Jedelsk´y ACM, 2023. doi: 10.1145/3564246.3585186. UR...

arXiv 2023

[8] [7]

Dreier, N

J. Dreier, N. M ¨ahlmann, and S. Toru ´nczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In B. Mohar, I. Shinkar, and R. O’Donnell, editors,Pro- ceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1550–1560. ACM, 2024. doi: 10.1145/3618260.36...

arXiv 2024