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 [6]. 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 [2].
Additional Metadata
Keywords treewidth, monadic second order logic of graphs, finite state tree automata, k-outerplanar graphs
ACM Models of Computation (acm F.1.1)
THEME Null option (theme 11)
Persistent URL dx.doi.org/10.4230/LIPIcs.IPEC.2015.175
Project Networks
Conference International Symposium on Parameterized and Exact Computation
Grant This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/024.002.003 - Networks
Citation
Jaffke, L, & Bodlaender, H.L. (2015). Definability Equals Recognizability for k-Outerplanar Graphs. In Proceedings of International Symposium on Parameterized and Exact Computation 2015 (IPEC 10) (pp. 175–186). doi:10.4230/LIPIcs.IPEC.2015.175