Definability equals recognizability of partial 3-trees

DOI10.1007/3-540-62559-3_20zbMath1539.68225MaRDI QIDQ6550548

D. Kaller

Publication date: 5 June 2024

zbMATH Keywords

tree decompositiontransitive closureouterplanar graphtree automatoninternal vertex

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Logic in computer science (03B70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Forbidden minors characterization of partial 3-trees
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Regularity and locality in \(k\)-terminal graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Linear-time computability of combinatorial problems on series-parallel graphs
• Linear-time computation of optimal subgraphs of decomposable graphs
• A linear time algorithm for finding tree-decompositions of small treewidth

This page was built for publication: Definability equals recognizability of partial 3-trees