Characterizations and algorithmic applications of chordal graph embeddings

DOI10.1016/S0166-218X(97)00041-3zbMath0887.05044WikidataQ55954280 ScholiaQ55954280MaRDI QIDQ1372739

Andreas Parra, Petra Scheffler

Publication date: 5 May 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

triangulationbandwidthembeddingtreewidthchordal graphinterval graphpathwidthasteroidal tripleseparator graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (49)

On claw-free asteroidal triple-free graphs ⋮ Minimal triangulations of graphs: a survey ⋮ Listing all the minimal separators of a 3-connected planar graph ⋮ Tree-decompositions with bags of small diameter ⋮ Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree ⋮ Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ The Smallest Classes of Binary and Ternary Matroids Closed under Direct Sums and Complements ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ Mixed Search Number of Permutation Graphs ⋮ A Characterisation of the Minimal Triangulations of Permutation Graphs ⋮ How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms ⋮ On groups with chordal power graph, including a classification in the case of finite simple groups ⋮ Approximating the treewidth of AT-free graphs. ⋮ Induced matchings in asteroidal triple-free graphs ⋮ Chordal embeddings of planar graphs ⋮ Approximating the path-distance-width for AT-free graphs and graphs in related classes ⋮ Faster parameterized algorithms for \textsc{Minimum Fill-in} ⋮ On treewidth approximations. ⋮ Searching for better fill-in ⋮ Efficiently enumerating minimal triangulations ⋮ On the complexity of computing treebreadth ⋮ Separator orders in interval, cocomparability, and AT-free graphs ⋮ Connected graph searching in chordal graphs ⋮ Minimal split completions ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Minimum fill-in of sparse graphs: kernelization and approximation ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ To Approximate Treewidth, Use Treelength! ⋮ Dynamic programming and planarity: improved tree-decomposition based algorithms ⋮ Fast minimal triangulation algorithm using minimum degree criterion ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ Finding cut-vertices in the square roots of a graph ⋮ Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions ⋮ On the domination search number ⋮ Unnamed Item ⋮ On a property of minimal triangulations ⋮ Exploiting variable sparsity in computing equilibria of biological dynamical systems by triangular decomposition ⋮ On the Number of Minimal Separators in Graphs ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Approximability of the Path-Distance-Width for AT-free Graphs ⋮ Unnamed Item ⋮ A CHARACTERIZATION OF k-TH POWERS P_n,k OF PATHS IN TERMS OF k-TREES ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds ⋮ Treewidth of planar graphs: connections with duality ⋮ Listing all potential maximal cliques of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Optimal node ranking of trees
• The NP-completeness of the bandwidth minimization problem
• Treewidth. Computations and approximations
• On the complexity of DNA physical mapping
• Claw-free graphs---a survey
• Triangulating graphs without asteroidal triples
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Representation of a finite graph by a set of intervals on the real line
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• The bandwidth problem for graphs and matrices—a survey
• Computing the Minimum Fill-In is NP-Complete
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• How to use the minimal separators of a graph for its chordal triangulation
• The Pathwidth and Treewidth of Cographs
• Treewidth and Pathwidth of Permutation Graphs
• A linear time algorithm for finding tree-decompositions of small treewidth
• Transitiv orientierbare Graphen
• Approximating the bandwidth for asteroidal triple-free graphs

This page was built for publication: Characterizations and algorithmic applications of chordal graph embeddings