Triangulating planar graphs while minimizing the maximum degree

DOI10.1007/3-540-55706-7_22zbMath1502.68234OpenAlexW1615212840WikidataQ59568017 ScholiaQ59568017MaRDI QIDQ5056146

Goos Kant, Hans L. Bodlaender

Publication date: 9 December 2022

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

Full work available at URL: https://doi.org/10.1007/3-540-55706-7_22

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

One strike against the min-max degree triangulation problem ⋮ Polygon decomposition for efficient construction of Minkowski sums

Cites Work

• How to draw a planar graph on a grid
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Finding a Smallest Augmentation to Biconnect a Graph
• Convex Representations of Graphs
• A Depth-First-Search Characterization of Planarity
• Efficient Planarity Testing
• Augmentation Problems
• Smallest Augmentations to Biconnect a Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item