2015
Definability Equals Recognizability for k-Outerplanar Graphs
Publication
Publication
Presented at the
International Symposium on Parameterized and Exact Computation, Patras, Greece
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 | |
---|---|
, , , | |
doi.org/10.4230/LIPIcs.IPEC.2015.175 | |
Networks | |
International Symposium on Parameterized and Exact Computation | |
Organisation | Algorithms and Complexity |
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 |