Chordal embeddings of planar graphs

DOI10.1016/S0012-365X(03)00230-9zbMath1029.05038MaRDI QIDQ1417569

Ioan Todinca, Frédéric Mazoit, Vincent Bouchitte

Publication date: 5 January 2004

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

zbMATH Keywords

Duality; Planar graphs; Treewidth

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

Related Items

On self-duality of branchwidth in graphs of bounded genus, Tree-width of hypergraphs and surface duality, Contracting planar graphs to contractions of triangulations, Dynamic programming and planarity: improved tree-decomposition based algorithms, Tree decomposition and discrete optimization problems: a survey, Tree-width of graphs and surface duality, THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS, Connected Graph Searching in Outerplanar Graphs, How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Call routing and the ratcatcher
• Characterizations and algorithmic applications of chordal graph embeddings
• Listing all potential maximal cliques of a graph
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Treewidth of Circular-Arc Graphs
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Treewidth of Chordal Bipartite Graphs
• Treewidth and Pathwidth of Permutation Graphs
• Approximating the bandwidth for asteroidal triple-free graphs