A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths

DOI10.1007/3-540-61228-9_106zbMath1412.68161OpenAlexW1506863176MaRDI QIDQ4645295

Stefan Arnborg, Andrzej Proskurowski

Publication date: 10 January 2019

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61228-9_106

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Structural characterization of families of graphs (05C75) Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Canonical representations of partial 2- and 3-trees
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Obstruction set isolation for the gate matrix layout problem
• Combinatorial algorithms on a class of graphs
• On simple characterizations of k-trees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A decomposition theorem for partially ordered sets
• Steiner trees, partial 2–trees, and minimum IFI networks
• Easy problems for tree-decomposable graphs
• Graph expressions and graph rewritings
• The Recognition of Series Parallel Digraphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• An algebraic theory of graph reduction
• Generalized finite automata theory with an application to a decision problem of second-order logic