Triangulating graphs without asteroidal triples

DOI10.1016/0166-218X(95)00095-9zbMath0856.68112OpenAlexW2045187717MaRDI QIDQ1917255

Rolf H. Möhring

Publication date: 7 July 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(95)00095-9

zbMATH Keywords

treewidthasteroidal triple

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Minimal triangulations of graphs: a survey, Representing a concept lattice by a graph, Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs, Characterizations and algorithmic applications of chordal graph embeddings, Independent sets in asteroidal triple-free graphs, Recognizing graphs without asteroidal triples, Two characterisations of the minimal triangulations of permutation graphs, On treewidth and minimum fill-in of asteroidal triple-free graphs, Triangulating multitolerance graphs, A Characterisation of the Minimal Triangulations of Permutation Graphs, Interval degree and bandwidth of a graph, Tree-width and path-width of comparability graphs of interval orders, Bandwidth on AT-free graphs, The complexity of subgraph isomorphism for classes of partial k-trees, Separator orders in interval, cocomparability, and AT-free graphs, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Boxicity and cubicity of asteroidal triple free graphs, Asteroidal triples of moplexes, On the interval completion of chordal graphs, Treewidth and minimum fill-in on permutation graphs in linear time, Tree-decompositions of small pathwidth, Tree-decompositions of small pathwidth, Treewidth and logical definability of graph products, On a property of minimal triangulations, A partial k-arboretum of graphs with bounded treewidth, Triangulating graphs with few \(P_4\)'s, On sparsification for computing treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tolerance graphs
• Decomposition by clique separators
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• On the pathwidth of chordal graphs
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Treewidth. Computations and approximations
• Triangulated graphs and the elimination process
• Representation of a finite graph by a set of intervals on the real line
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Asteroidal Triple-Free Graphs
• Treewidth and pathwidth of permutation graphs
• The Pathwidth and Treewidth of Cographs