Graphs with Branchwidth at Most Three

1999/08/01 by Hans L. Bodlaender, Hans L Bodlaender, Dimitrios M. Thilikos +1 · 28 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Clique-sum #Cograph #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Indifference graph #Line graph #Mathematics #Maximal independent set #Modular decomposition #Partial k-tree #Pathwidth #Split graph #Treewidth

paper · open access · doi:10.1006/jagm.1999.1011

published in Journal of Algorithms 32(2), 167-194 (Elsevier BV)

crossref issued 1999/08/01 · crossref published 1999/08/01 · crossref published-print 1999/08/01 · openalex publication_date 1999/08/01 · crossref created 2002/10/06 · crossref deposited 2019/05/07 · openalex created_date 2025/10/10 · crossref indexed 2025/11/18 · openalex updated_date 2026/07/22

Citations

• The intersection graphs of subtrees in trees are exactly the chordal graphs
• A characterization of partial 3‐trees
• Complexity of Finding Embeddings in a k-Tree
• A partial k-arboretum of graphs with bounded treewidth
• Forbidden minors characterization of partial 3-trees

Cited by

• Constructive linear time algorithms for branchwidth
• Tour Merging via Branch-Decomposition
• Branch-decomposition [wikipedia]
• Forbidden graph characterization [wikipedia]