Document Open Access Logo

Definability Equals Recognizability for k-Outerplanar Graphs

Authors Lars Jaffke, Hans L. Bodlaender

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.175.pdf
  • Filesize: 0.55 MB
  • 12 pages

Document Identifiers

Author Details

Lars Jaffke
Hans L. Bodlaender

Cite As Get BibTex

Lars Jaffke and Hans L. Bodlaender. Definability Equals Recognizability for k-Outerplanar Graphs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 175-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.IPEC.2015.175

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.

Subject Classification

Keywords
  • treewidth
  • monadic second order logic of graphs
  • finite state tree automata
  • $k$-outerplanar graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308-340, 1991. Google Scholar
  2. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1-2):1-45, 1998. Google Scholar
  3. Hans L. Bodlaender, Pinar Heggernes, and Jan Arne Telle. Recognizability equals definability for graphs of bounded treewidth and bounded chordality. In Proceedings EUROCOMB 2015, Electronic Notes in Discrete Mathematics. Elsevier, 2015. Google Scholar
  4. Richard B. Borie, R. Gary Parker, and Craig A. Tovey. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica, 7(1-6):555-581, 1992. Google Scholar
  5. J. Richard Büchi. Weak second-order arithmetic and finite automata. Mathematical Logic Quarterly, 6(1-6):66-92, 1960. Google Scholar
  6. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. Google Scholar
  7. Bruno Courcelle. The monadic second-order logic of graphs V: On closing the gap between definability and recognizability. Theoretical Computer Science, 80(2):153-202, 1991. Google Scholar
  8. Bruno Courcelle. The monadic second order logic of graphs VI: On several representations of graphs by relational structures. Discrete Applied Mathematics, 54(2-3):117-149, 1994. Google Scholar
  9. Bruno Courcelle. The monadic second-order logic of graphs VIII: Orientations. Annals of Pure and Applied Logic, 72(2):103-143, 1995. Google Scholar
  10. Bruno Courcelle. The monadic second-order logic of graphs XI: Hierarchical decompositions of connected graphs. Theoretical Computer Science, 224(1-2):38-53, 1999. Google Scholar
  11. Bruno Courcelle. The monadic second-order logic of graphs XII: Planar graphs and planar maps. Theoretical Computer Science, 237(1-2):1-32, 2000. Google Scholar
  12. Reinhard Diestel. Graph Theory. Number 173 in Graduate Texts in Mathematics. Springer, 4th edition, 2012. Corrected reprint. Google Scholar
  13. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  14. Lars Jaffke and Hans L. Bodlaender. Definability equals recognizability for k-outerplanar graphs. ArXiv e-prints, 2015. http://arxiv.org/abs/1509.08315. Google Scholar
  15. Valentine Kabanets. Recognizability equals definability for partial k-paths. In Proceedings ICALP 1997, volume 1256 of LNCS, pages 805-815. Springer, 1997. Google Scholar
  16. Damon Kaller. Definability equals recognizability of partial 3-trees and k-connected partial k-trees. Algorithmica, 27(3-4):348-381, 2000. Google Scholar
  17. Ioannis Katsikarelis. Computing bounded-width tree and branch decompositions of k-outerplanar graphs. ArXiv e-prints, 2013. http://arxiv.org/abs/1301.5896. Google Scholar
  18. Denis Lapoire. Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width. In Proceedings STACS 1998, volume 1373 of LNCS, pages 618-628. Springer, 1998. Google Scholar
  19. William T. Tutte. Connectivity in Graphs. University of Toronto Press, 1966. Google Scholar
  20. William T. Tutte. Graph Theory, volume 21 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, 1984. Google Scholar
  21. Hassler Whitney. Congruent graphs and the connectivity of graphs. American Journal of Mathematics, 54:150-168, 1932. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact