Minimal elimination of planar graphs

DOI10.1007/BFB0054369MaRDI QIDQ5054857zbMATH OpenFDO

Authors Elias Dahlhaus

Publication date 9 December 2022

Published in Algorithm Theory — SWAT'98 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0054369

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Minimal elimination ordering for graphs of bounded degree
• scientific article; zbMATH DE number 1145349
• Minimal fill in O(\(n^{2.69}\)) time
• scientific article; zbMATH DE number 1107728
• Fast Computation of Minimal Fill Inside A Given Elimination Ordering

Cites work

• scientific article; zbMATH DE number 554763 (Why is no real title available?)
• scientific article; zbMATH DE number 1107728 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A characterisation of rigid circuit graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
• Characterizations of strongly chordal graphs
• Computing the Minimum Fill-In is NP-Complete
• How to use the minimal separators of a graph for its chordal triangulation
• Making an arbitrary filled graph minimal by removing fill edges
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Triangulated graphs and the elimination process

Cited in

(9)

• Minimal elimination ordering for graphs of bounded degree
• Elimination properties for minimal dominating sets of graphs
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Minimal triangulations of graphs: a survey
• Revisiting decomposition by clique separators
• Obtaining a planar graph by vertex deletion
• Making an arbitrary filled graph minimal by removing fill edges
• scientific article; zbMATH DE number 1145349 (Why is no real title available?)
• Minor-universal planar graphs without accumulation points

This page was built for publication: Minimal elimination of planar graphs

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