REVIEW 2 cited by
Graph classes through the lens of logic
Not yet reviewed by Pith; the record is open.
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
read the original abstract
Graph transformations definable in logic can be described using the notion of transductions. By understanding transductions as a basic embedding mechanism, which captures the possibility of encoding one graph in another graph by means of logical formulas, we obtain a new perspective on the landscape of graph classes and of their properties. The aim of this survey is to give a comprehensive presentation of this angle on structural graph theory. We first give a logic-focused overview of classic graph-theoretic concepts, such as treedepth, shrubdepth, treewidth, cliquewidth, twin-width, bounded expansion, and nowhere denseness. Then, we present recent developments related to notions defined purely through transductions, such as monadic stability, monadic dependence, and classes of structurally sparse graphs.
Forward citations
Cited by 2 Pith papers
-
Set-defined graph classes: $\chi$-boundedness meets tropical algebra
Full set-defined classes are polynomially χ-bounded iff they avoid high-chromatic shift graphs, decidable via tropical feasibility dual to mean-payoff games.
-
k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs
Sparse graph classes are first-order transducible from graphs on a fixed surface if and only if they admit a new type of bounded fan-crossing drawing on that surface.
Discussion (0). Sign in to comment.