A partial k-arboretum of graphs with bounded treewidth

1998/12/01 by Hans L. Bodlaender · 32 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Artificial intelligence #Bounded function #Chordal graph #Class (philosophy) #Clique-sum #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Line graph #Mathematics #Partial k-tree #Pathwidth #Tree-depth #Treewidth #Upper and lower bounds

paper · doi:10.1016/s0304-3975(97)00228-4

crossref issued 1998/12/01 · crossref published 1998/12/01 · crossref published-print 1998/12/01 · openalex publication_date 1998/12/01 · crossref created 2003/05/01 · crossref deposited 2019/04/29 · openalex created_date 2025/10/10 · crossref indexed 2026/07/24 · openalex updated_date 2026/07/25

Citations

• Characterizations of outerplanar graphs
• Graph minors. III. Planar tree-width
• Linear-time computation of optimal subgraphs of decomposable graphs
• Graph minors. I. Excluding a forest
• Graph Minors. XVI. Excluding a non-planar graph
• Graph minors. V. Excluding a planar graph
• Complexity of Finding Embeddings in a k-Tree
• Approximation algorithms for NP-complete problems on planar graphs

Cited by

• An annotated bibliography on guaranteed graph searching
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• A c^k n 5-Approximation Algorithm for Treewidth
• Large Induced Subgraphs via Triangulations and CMSO
• Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
• The pagenumber of k-trees is O(k)
• Pathwidth of outerplanar graphs
• Pathwidth of Planar and Line Graphs
• Approximation of pathwidth of outerplanar graphs
• Improved approximation algorithms for minimum-weight vertex separators
• Exact Algorithms for Treewidth and Minimum Fill-In
• Pathwidth of Circular-Arc Graphs
• Counting models for 2SAT and 3SAT formulae
• Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
• Graph Subcolorings: Complexity and Algorithms
• Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
• Computing the Girth of a Planar Graph in Linear Time
• Approximating the maximum clique minor and some subgraph homeomorphism problems
• Algorithms for Graphs Embeddable with Few Crossings per Edge
• A Note on Exact Algorithms for Vertex Ordering Problems on Graphs
• Layout of Graphs with Bounded Tree-Width
• Distinct Distances in Graph Drawings
• The Behavior of Clique-Width under Graph Operations and Graph Transformations
• MSOL-Definability Equals Recognizability for Halin Graphs and Bounded Degree k-Outerplanar Graphs
• On tree-partition-width
• Exact square coloring of subcubic planar graphs
• Characterizing width two for variants of treewidth
• Pathwidth of cubic graphs and exact algorithms
• Minimum Cost Mirror Sites Using Network Coding: Replication versus Coding at the Source Nodes
• Interval graph [wikipedia]
• Pathwidth [wikipedia]
• Treewidth [wikipedia]