A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators

2006/01/01 by Christian Knauer, Andreas Spillner · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Bowyer–Watson algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Convex hull #Delaunay triangulation #Discrete mathematics #Geometry #Graph #Mathematics #Minimum-weight triangulation #Regular polygon #Triangulation

paper · doi:10.1007/11917496_5

published in Lecture Notes in Computer Science, 49-57 (Springer Berlin Heidelberg)

crossref issued 2006/01/01 · crossref published 2006/01/01 · crossref published-print 2006/01/01 · openalex publication_date 2006/01/01 · crossref created 2006/10/18 · crossref deposited 2021/04/27 · crossref indexed 2024/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Citations

• A branch-and-cut approach for minimum weight triangulation
• Applications of a Planar Separator Theorem
• Reduced constants for simple cycle graph separation
• A Separator Theorem for Planar Graphs
• Finding small simple cycle separators for 2-connected planar graphs
• Graph separators: a parameterized view
• Parameterized Complexity

Cited by

• Minimum-weight triangulation [wikipedia]