Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We present a linear-time algorithm for deciding first-order logic (FOL) properties in classes of graphs with bounded expansion. Many natural classes of graphs have bounded expansion; for instance, graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We also develop an almost linear-time algorithm for deciding FOL properties in classes of graphs with locally bounded expansion; those include classes of graphs with locally bounded tree-width or locally excluding a minor.

More generally, we design a dynamic data structure for graphs belonging to a class $cal G$ of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FOL property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their addition results in a graph in $cal G$. In addition, we design dynamic data structure for testing $Sigma_1$-properties or the existence of short paths between prescribed vertices in such classes of graphs. All our results hold for relational structures.

Questions and Answers

You need to be logged in to be able to post here.