Chordal embeddings of planar graphs

DOI10.1016/S0012-365X(03)00230-9zbMATH Open1029.05038MaRDI QIDQ1417569FDOQ1417569

Authors: Ioan Todinca, Vincent Bouchitté, Frédéric Mazoit 

Publication date: 5 January 2004

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

Recommendations

• Tree-width of hypergraphs and surface duality
• Tree-width of graphs and surface duality
• Pathwidth of planar and line graphs
• Surfaces, tree-width, clique-minors, and partitions
• scientific article; zbMATH DE number 1500196

zbMATH Keywords

DualityPlanar graphsTreewidth

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Call routing and the ratcatcher
• Complexity of Finding Embeddings in a k-Tree
• Title not available (Why is that?)
• Graph minors. II. Algorithmic aspects of tree-width
• Listing all potential maximal cliques of a graph
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth and Pathwidth of Permutation Graphs
• Graph minors. III. Planar tree-width
• Treewidth of Chordal Bipartite Graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Title not available (Why is that?)
• Treewidth of Circular-Arc Graphs
• Approximating the bandwidth for asteroidal triple-free graphs
• Title not available (Why is that?)

Cited In (15)

• Chords of longest circuits in locally planar graphs
• Tree decomposition and discrete optimization problems: a survey
• On self-duality of branchwidth in graphs of bounded genus
• Tree-width of hypergraphs and surface duality
• Dynamic programming and planarity: improved tree-decomposition based algorithms
• On chordal and perfect plane near-triangulations
• On the biplanarity of blowups
• Connected Graph Searching in Outerplanar Graphs
• How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
• Tree-width of graphs and surface duality
• Contracting planar graphs to contractions of triangulations
• The point-set embeddability problem for plane graphs
• A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem
• Title not available (Why is that?)
• Branchwidth is \((1, g)\)-self-dual

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

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