Definability equals recognizability for k-outerplanar graphs

DOI10.4230/LIPICS.IPEC.2015.175MaRDI QIDQ5363771zbMATH OpenOpenAlexFDO

Authors Lars Jaffke, Hans L. Bodlaender

Publication date 29 September 2017

Full work available at URL https://arxiv.org/abs/1509.08315

zbMATH Keywords

\(k\)-outerplanar graphsfinite-state tree automatamonadic second-order logic of graphstreewidth

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Abstract: One of the most famous algorithmic meta-theorems states that every graph property that can be defined by a sentence in counting monadic second order logic (CMSOL) can be checked in linear time for graphs of bounded treewidth, which is known as Courcelle's Theorem. These algorithms are constructed as finite state tree automata, and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. We prove this conjecture for $k$-outerplanar graphs, which are known to have treewidth at most $3k-1$.

Recommendations

• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• Definability equals recognizability for graphs of bounded treewidth
• Definability equals recognizability of partial 3-trees and k-connected partial k-trees
• scientific article; zbMATH DE number 1136093
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability

Cited in

(9)

• Definability equals recognizability of partial 3-trees and k-connected partial k-trees
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• Causality in bounded Petri nets is MSO definable
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• Recognizability equals definability for partial k-paths
• Definability equals recognizability for graphs of bounded treewidth
• On supergraphs satisfying CMSO properties
• Definability equals recognizability of partial 3-trees
• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity

This page was built for publication: Definability equals recognizability for \(k\)-outerplanar graphs

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