One strike against the min-max degree triangulation problem

DOI10.1016/0925-7721(93)90003-OMaRDI QIDQ685602zbMATH OpenFDO

Authors Klaus Jansen

Publication date 17 October 1993

Published in Computational Geometry (Search for Journal in Brave)

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)

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Edge insertion for optimal triangulations
• Mesh relaxation: A new technique for improving triangulations
• Planar Formulae and Their Uses
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Triangulating planar graphs while minimizing the maximum degree

Cited in

(10)

• Plane graphs with parity constraints
• Computational complexity of the vertex cover problem in the class of planar triangulations
• Planar subgraphs without low-degree nodes
• Euler transformation of polyhedral complexes
• 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
• 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)