Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
Publication:2403697
DOI10.1016/j.ejc.2017.06.025zbMath1369.05048OpenAlexW2737935917WikidataQ59567372 ScholiaQ59567372MaRDI QIDQ2403697
Lars Jaffke, Jan Arne Telle, Pinar Heggernes, Hans L. Bodlaender
Publication date: 11 September 2017
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2017.06.025
Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Algebraic theory of languages and automata (68Q70) Structural characterization of families of graphs (05C75) Interpolation, preservation, definability (03C40)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recognizability equals definability for graphs of bounded treewidth and bounded chordality
- Fundamentals of parameterized complexity
- Safe separators for treewidth
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Characterizations of outerplanar graphs
- A partial k-arboretum of graphs with bounded treewidth
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- The monadic second-order logic of graphs. X: Linear orderings
- Characterizations and algorithmic applications of chordal graph embeddings
- The monadic second-order logic of graphs. XII: Planar graphs and planar maps
- Definability equals recognizability of partial 3-trees and \(k\)-connected partial \(k\)-trees
- The monadic second-order logic of graphs. VIII: Orientations
- Algorithmic graph theory and perfect graphs
- The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Über eine Eigenschaft der ebenen Komplexe
- Monadic second-order definable graph orderings
- Myhill-Nerode Methods for Hypergraphs
- Linear Automaton Transformations
- Weak Second‐Order Arithmetic and Finite Automata
- Easy problems for tree-decomposable graphs
- Congruent Graphs and the Connectivity of Graphs
- Recognizability equals definability for partial k-paths
- Definability equals recognizability for graphs of bounded treewidth
- Definability Equals Recognizability for $k$-Outerplanar Graphs
- Trees in Polyhedral Graphs
This page was built for publication: Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
