One strike against the min-max degree triangulation problem

DOI10.1016/0925-7721(93)90003-OzbMATH Open0779.68088MaRDI QIDQ685602FDOQ685602

Klaus Jansen

Publication date: 17 October 1993

Published in: Computational Geometry (Search for Journal in Brave)

Recommendations

• Triangulating planar graphs while minimizing the maximum degree
• Triangulating planar graphs while minimizing the maximum degree
• Minimum-weight triangulation is NP-hard
• Computational geometry column 40
• New results for the minimum weight triangulation problem

zbMATH Keywords

triangulationNP-completegeometric graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• Planar Formulae and Their Uses
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Mesh relaxation: A new technique for improving triangulations
• Edge insertion for optimal triangulations
• Triangulating planar graphs while minimizing the maximum degree

Cited In (8)

• Plane graphs with parity constraints
• Higher order Delaunay triangulations
• Triangulating planar graphs while minimizing the maximum degree
• Minimum degree triangulation for rectangular domains
• Profile minimization on triangulated triangles
• Augmenting Geometric Graphs with Matchings
• Euler Transformation of Polyhedral Complexes
• Plane Graphs with Parity Constraints

This page was built for publication: One strike against the min-max degree triangulation problem

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