Published March 20, 2017
| Version v1
Publication
Triangulations without pointed spanning trees
Description
Problem 50 in the Open Problems Project 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.
Abstract
Acciones Integradas 2003-2004Abstract
Austrian Fonds zur Förderung der Wissenschaftlichen ForschungAdditional details
Identifiers
- URL
- https://idus.us.es/handle/11441/56020
- URN
- urn:oai:idus.us.es:11441/56020
Origin repository
- Origin repository
- USE