Minimal elimination of planar graphs

DOI10.1007/BFb0054369zbMath1502.68219MaRDI QIDQ5054857

Elias Dahlhaus

Publication date: 9 December 2022

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

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Minimal triangulations of graphs: a survey ⋮ Revisiting Decomposition by Clique Separators ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs

Cites Work

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

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