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

treewidth\(k\)-outerplanar graphsmonadic second-order logic of graphsfinite-state tree automata

Mathematics Subject Classification ID

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

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

(8)

• scientific article; zbMATH DE number 7471674 (Why is no real title available?)
• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
• Recognizability equals definability for partial k-paths
• Causality in bounded Petri nets is MSO definable
• Definability equals recognizability for graphs of bounded treewidth
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• Definability equals recognizability of partial 3-trees
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees

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)