Chordal embeddings of planar graphs

DOI10.1016/S0012-365X(03)00230-9MaRDI QIDQ1417569zbMATH OpenFDO

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

Publication date 5 January 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(03)00230-9

zbMATH Keywords

DualityPlanar graphsTreewidth

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(17)

• On chordal and perfect plane near-triangulations
• 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
• On self-duality of branchwidth in graphs of bounded genus
• Tree-width of hypergraphs and surface duality
• A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem
• On supergraphs satisfying CMSO properties
• Branchwidth is \((1, g)\)-self-dual
• Contracting planar graphs to contractions of triangulations
• On the biplanarity of blowups
• Structure and independence in hyperbolic uniform disk graphs
• A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
• Chords of longest circuits in locally planar graphs
• Dynamic programming and planarity: improved tree-decomposition based algorithms

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)