The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs

DOI10.1016/S0304-3975(98)00306-5MaRDI QIDQ1960417zbMATH OpenFDO

Authors Bruno Courcelle

Publication date 12 January 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(98)00306-5

zbMATH Keywords

3-connected graphblockdirected acyclic graphexpressive power of monadic second-order logicgraph theorytreeunique decompositions of connected graphs

Mathematics Subject Classification ID

Second- and higher-order model theory (03C85) Connectivity (05C40)

Review text

[For the previous parts see Zbl 0877.68087, Zbl 0872.03026, and the citations given there.] This is the eleventh paper in the author's extensive study of the expressive power of monadic second-order (MSO) logic in the realm of graph theory. Here he proves that the unique decompositions of connected graphs introduced by W. Tutte are definable by MSO-formulas. For obtaining this result it is first shown that every 2-dag has a unique canonical decomposition which is MSO-definable; a 2-dag is a (finite) directed acyclic graph in which every vertex lies on a path from a fixed source vertex to a fixed target vertex.

Recommendations

• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• Graph decompositions definable in monadic second-order logic
• The definition in monadic second-order logic of modular decompositions of ordered graphs
• Graph equivalences and decompositions definable in monadic second-order logic. The case of circle graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues

Cites work

• Complement reducible graphs
• Definability equals recognizability of partial 3-trees and k-connected partial k-trees
• Handbook of Graph Grammars and Computing by Graph Transformation
• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 1136093 (Why is no real title available?)
• Monadic second-order definable graph transductions: a survey
• Monadic second-order evaluations on tree-decomposable graphs
• Recognising k-connected hypergraphs in cubic time
• Recognizability equals definability for partial k-paths
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. VIII: Orientations
• The monadic second-order logic of graphs. X: Linear orderings

Cited in

(15)

• The monadic second-order logic of graphs. VII: Graphs as relational structures
• A monadic second-order definition of the structure of convex hypergraphs.
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• Graph decompositions definable in monadic second-order logic
• scientific article; zbMATH DE number 1290983 (Why is no real title available?)
• GETGRATS: a summary of scientific results (with annotated bibliography)
• Kernelization of Whitney switches
• On zero-one and convergence laws for graphs embeddable on a fixed surface
• scientific article; zbMATH DE number 7204410 (Why is no real title available?)
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• Computer Science Logic
• Kernelization of Whitney Switches
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• CMSO-transducing tree-like graph decompositions

This page was built for publication: The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1960417)