Pith. sign in

REVIEW 3 cited by

3D-grids are not transducible from planar graphs

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2501.07558 v1 pith:EVDLOBNC submitted 2025-01-13 cs.LO cs.DMmath.CO

Jakub Gajarský , Micha{l} Pilipczuk , Filip Pokrývka This is my paper · ORCID
classification cs.LOcs.DMmath.CO
keywords classgraphsboundedd-gridsdecompositionseulergenusgraph
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We prove that the class of 3D-grids is cannot be transduced from planar graphs, and more generally, from any class of graphs of bounded Euler genus. To prove our result, we introduce a new structural tool called slice decompositions, and show that every graph class transducible from a class of graphs of bounded Euler genus is a perturbation of a graph class that admits slice decompositions.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. First-order transducibility among classes of sparse graphs

    cs.LO 2025-05 accept novelty 8.0 of 10

    Treewidth t+1 graphs are not first-order transducible from treewidth t graphs, with analogous separations for Hadwiger number and for treewidth 4 graphs from planar graphs.

  2. Short Paths in the Planar Graph Product Structure Theorem

    math.CO 2025-02 conditional novelty 8.0 of 10

    Every n-vertex planar graph is contained in H ⊠ P ⊠ K_c for some planar H of treewidth 3 and a path P of length O((tw(G)+1)^(1-ε) n^ε).

  3. Transductions of Graph Classes Admitting Product Structure

    cs.LO 2025-01 accept novelty 7.0 of 10

    Transductions of product-structured classes are, up to perturbation, exactly bounded path-power clique-width classes, which excludes 3D grids and pinned grid families.

Pith tools