Treewidth and pathwidth of permutation graphs

1993/01/01 by Hans L. Bodlaender, Hans Bodlaender, Ton Kloks +1 · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithms and Data Compression #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Line graph #Mathematics #Partial k-tree #Pathwidth #Permutation (music) #Permutation graph #Physics #Tree-depth #Treewidth

paper · doi:10.1007/3-540-56939-1_66

crossref issued 1993/01/01 · crossref published 1993/01/01 · crossref published-print 1993/01/01 · openalex publication_date 1993/01/01 · crossref published-online 2005/05/28 · crossref created 2012/02/26 · crossref deposited 2020/11/17 · openalex created_date 2025/10/10 · crossref indexed 2025/10/16 · openalex updated_date 2026/08/01

Citations

• Representation of a finite graph by a set of intervals on the real line
• Linear time algorithms for NP-hard problems restricted to partial k-trees
• Permutation Graphs and Transitive Graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A survey
• Complexity of Finding Embeddings in a k-Tree
• Finding approximate separators and computing tree width quickly

Cited by

• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Pathwidth [wikipedia]