Pith. sign in

REVIEW 1 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
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). Sign in to comment.

Forward citations

Cited by 1 Pith paper

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.

Pith tools