Graph classes through the lens of logic

2025/01/07 by Pilipczuk, Michał · 3 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2501.04166

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.

Cited by

• k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs
• First-order transducibility among classes of sparse graphs
• Strong odd colorings in graph classes of bounded expansion
• Separability Properties of Monadically Dependent Graph Classes

Related

• On first-order transductions of classes of graphs
• Treelike decompositions for transductions of sparse graphs
• Structural properties of the first-order transduction quasiorder
• Nowhere dense graph classes and algorithmic applications. A tutorial at\n Highlights of Logic, Games and Automata 2019
• Transducing paths in graph classes with unbounded shrubdepth