A Characterisation of the Minimal Triangulations of Permutation Graphs

DOI10.1007/978-3-540-74839-7_10MaRDI QIDQ3508558zbMATH OpenOpenAlexFDO

Authors Daniel Meister

Publication date 1 July 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74839-7_10

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Two characterisations of the minimal triangulations of permutation graphs
• Treewidth and minimum fill-in on permutation graphs in linear time
• Minimal triangulations of graphs: a survey
• Treewidth and Pathwidth of Permutation Graphs
• Characterizations and algorithmic applications of chordal graph embeddings

Cites work

• A characterisation of rigid circuit graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• On rigid circuit graphs
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Representations of chordal graphs as subtrees of a tree
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The Pathwidth and Treewidth of Cographs
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Triangulating graphs without asteroidal triples

Cited in

(4)

• Two characterisations of the minimal triangulations of permutation graphs
• Restricted vertex multicut on permutation graphs
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Treewidth and minimum fill-in on permutation graphs in linear time

This page was built for publication: A Characterisation of the Minimal Triangulations of Permutation Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3508558)