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

DOI10.1016/S0304-3975(98)00306-5zbMath0938.03015MaRDI QIDQ1960417

Bruno Courcelle

Publication date: 12 January 2000

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

zbMATH Keywords

treeblockgraph theorydirected acyclic graph3-connected graphexpressive power of monadic second-order logicunique decompositions of connected graphs

Mathematics Subject Classification ID

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

Related Items

Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees, A monadic second-order definition of the structure of convex hypergraphs., Unnamed Item, GETGRATS, Unnamed Item, The monadic second-order logic of graphs. XII: Planar graphs and planar maps, Kernelization of Whitney Switches, Kernelization of Whitney Switches, Graph decompositions definable in monadic second-order logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognising \(k\)-connected hypergraphs in cubic time
• Monadic second-order evaluations on tree-decomposable graphs
• Complement reducible graphs
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Monadic second-order definable graph transductions: a survey
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• The monadic second-order logic of graphs. X: Linear orderings
• Definability equals recognizability of partial 3-trees and \(k\)-connected partial \(k\)-trees
• The monadic second-order logic of graphs. VIII: Orientations
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Handbook of Graph Grammars and Computing by Graph Transformation
• Recognizability equals definability for partial k-paths