Characterizations and algorithmic applications of chordal graph embeddings
type: Item
instance of: scholarly article
title: Characterizations and algorithmic applications of chordal graph embeddings
zbMATH Open document ID: 0887.05044
DOI: 10.1016/S0166-218X(97)00041-3
author: Andreas Parra
author: Petra Scheffler
published in: Discrete Applied Mathematics
publication date: 1998-05-05T00:00:00Z
full work available at URL: dam
review text: An embedding of a graph into a chordal graph (a graph with no chordless cycle of length greater than three) is a triangulation. Several classes of graphs are characterized by their minimal triangulations. The main tool for obtaining these results is the definition of a separator graph for a graph \(G\) which allows a 1-1 correspondence between the minimal triangulations of \(G\) and the maximal cliques of its separator graph. It is shown e.g. that a graph is AT-free (claw-free AT-free, a cograph) iff every minimal triangulation is an interval graph (proper interval graph, trivially perfect graph). Some algorithmic consequences for graph parameters that are related to triangulation problems (e.g. the bandwidth, treewidth, pathwidth) are also derived.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1088862
zbMATH Keywords: asteroidal triple
zbMATH Keywords: embedding
zbMATH Keywords: chordal graph
zbMATH Keywords: triangulation
zbMATH Keywords: separator graphs
zbMATH Keywords: interval graph
zbMATH Keywords: bandwidth
zbMATH Keywords: treewidth
zbMATH Keywords: pathwidth
Wikidata QID: Q55954280
reviewed by: Martin Middendorf
MaRDI profile type: Publication
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Easy problems for tree-decomposable graphs
cites work: A linear time algorithm for finding tree-decompositions of small treewidth
cites work: Q4291429
cites work: Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
cites work: Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
cites work: Treewidth and Pathwidth of Permutation Graphs
cites work: The Pathwidth and Treewidth of Cographs
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Q3676177
cites work: Q3140414
cites work: On rigid circuit graphs
cites work: Claw-free graphs---a survey
cites work: Transitiv orientierbare Graphen
cites work: Q4198056
cites work: Q3328583
cites work: On the complexity of DNA physical mapping
cites work: Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
cites work: Optimal node ranking of trees
cites work: Treewidth. Computations and approximations
cites work: Q4942656
cites work: Approximating the bandwidth for asteroidal triple-free graphs
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Q3477966
cites work: Triangulating graphs without asteroidal triples
cites work: The NP-completeness of the bandwidth minimization problem
cites work: How to use the minimal separators of a graph for its chordal triangulation
cites work: Q5588432
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Computing the Minimum Fill-In is NP-Complete
description: scientific article; zbMATH DE number 1088862