2026-07-22T17:01:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5581 2024-03-06T10:36:35Z ddc:004 open_access

Definability Equals Recognizability for k-Outerplanar Graphs Jaffke, Lars Bodlaender, Hans L. treewidth monadic second order logic of graphs finite state tree automata $k$-outerplanar graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lars Jaffke and Hans L. Bodlaender 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.175 urn:nbn:de:0030-drops-55815 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.175 eng https://creativecommons.org/licenses/by/3.0/legalcode