Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414332 | Computational Geometry | 2008 | 5 Pages |
Abstract
Problem 50 in the Open Problems Project of the computational geometry community asks whether any triangulation on a point set in the plane contains a pointed spanning tree as a subgraph. We provide a counterexample. As a consequence we show that there exist triangulations which require a linear number of edge flips to become Hamiltonian.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics