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

DualityPlanar graphsTreewidth

Mathematics Subject Classification ID

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

Related Items (12)

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

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

This page was built for publication: Chordal embeddings of planar graphs